Generalizations of Swierczkowski’s lemma and the arity gap of finite functions
Lehtonen, Erkko; Couceiro, Miguel (2009), Generalizations of Swierczkowski’s lemma and the arity gap of finite functions, Discrete Mathematics, 309, 20, p. 5905-5912. http://dx.doi.org/10.1016/j.disc.2009.04.009
Type
Article accepté pour publication ou publiéExternal document link
http://arxiv.org/abs/0712.1753Date
2009Journal name
Discrete MathematicsVolume
309Number
20Publisher
Elsevier
Pages
5905-5912
Publication identifier
Metadata
Show full item recordAbstract (EN)
Świerczkowski’s lemma–as it is usually formulated–asserts that if f:An→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.Subjects / Keywords
Semiprojection; Arity gap; Essential variables; Variable identification minors; Variable substitution; Pseudo-Boolean functions; Boolean functions; Finite functionsRelated items
Showing items related by title and author.
-
Lehtonen, Erkko; Couceiro, Miguel; Couceiro, Miguel (2008) Communication / Conférence
-
Couceiro, Miguel; Lehtonen, Erkko (2016) Article accepté pour publication ou publié
-
Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel (2012) Article accepté pour publication ou publié
-
Lehtonen, Erkko; Couceiro, Miguel (2011) Communication / Conférence
-
Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel (2012) Article accepté pour publication ou publié