| dc.contributor.author | Couceiro, Miguel | |
| dc.contributor.author | Lehtonen, Erkko | |
| dc.date.accessioned | 2012-09-28T07:53:55Z | |
| dc.date.available | 2012-09-28T07:53:55Z | |
| dc.date.issued | 2016 | |
| dc.identifier.issn | 1542-3980 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/10321 | |
| dc.language.iso | en | en |
| dc.subject | variable substitution | |
| dc.subject | Boolean function | |
| dc.subject | essential variable | |
| dc.subject | arity gap | |
| dc.subject | Finite function | |
| dc.subject.ddc | 512 | en |
| dc.title | On the arity gap of finite functions: results and applications | |
| dc.type | Article accepté pour publication ou publié | |
| dc.contributor.editoruniversityother | Universite du Luxembourg; | |
| dc.description.abstracten | Let A be a finite set and B an arbitrary set with at least two elements. The arity gap of a function f:An→B is the minimum decrease in the number of essential variables when essential variables of f are identified. A non-trivial fact is that the arity gap of such B-valued functions on A is at most |A|. Even less trivial to verify is the fact that the arity gap of B-valued functions on A with more than |A| essential variables is at most 2. These facts ask for a classification of B-valued functions on A in terms of their arity gap. In this paper, we survey what is known about this problem. We present a general characterization of the arity gap of B-valued functions on A and provide explicit classifications of the arity gap of Boolean and pseudo-Boolean functions. Moreover, we reveal unsettled questions related to this topic, and discuss links and possible applications of some results to other subjects of research. | |
| dc.relation.isversionofjnlname | Journal of Multiple-Valued Logic and Soft Computing | |
| dc.relation.isversionofjnlvol | 27 | |
| dc.relation.isversionofjnlissue | 2-3 | |
| dc.relation.isversionofjnldate | 2016 | |
| dc.relation.isversionofjnlpages | 193-207 | |
| dc.relation.isversionofjnlpublisher | OCP Science | |
| dc.subject.ddclabel | Algèbre | en |
| dc.relation.forthcoming | oui | en |
| dc.relation.forthcomingprint | non | en |
| dc.description.ssrncandidate | non | |
| dc.description.halcandidate | oui | |
| dc.description.readership | recherche | |
| dc.description.audience | International | |
| dc.relation.Isversionofjnlpeerreviewed | non | |
| dc.date.updated | 2016-12-03T15:57:04Z | |
