Reference : Generalizations of Świerczkowski’s lemma and the arity gap of finite functions
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Generalizations of Świerczkowski’s lemma and the arity gap of finite functions
Couceiro, Miguel mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]
Lehtonen, Erkko mailto [Tampere University of Technology, Finland]
Discrete Mathematics
Elsevier B.V.
Yes (verified by ORBilu)
[en] finite functions ; Boolean functions ; pseudo-Boolean functions ; variable substitution ; variable identification minors ; essential variables ; arity gap ; semiprojection
[en] Świerczkowski’s lemma–as it is usually formulated–asserts that if f:Aⁿ→A is an operation on a finite set A, n≥4, and every operation obtained from f by identifying a pair of variables is a projection, then f is a semiprojection. We generalize this lemma in various ways. First, it is extended to B-valued functions on A instead of operations on A and to essentially at most unary functions instead of projections. Then we characterize the arity gap of functions of small arities in terms of quasi-arity, which in turn provides a further generalization of Świerczkowski’s lemma. Moreover, we explicitly classify all pseudo-Boolean functions according to their arity gap. Finally, we present a general characterization of the arity gaps of B-valued functions on arbitrary finite sets A.

File(s) associated to this reference

Fulltext file(s):

Limited access
GeneralizationsSwierczkowski.pdfAuthor postprint303.26 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.