ON THE EFFECT OF VARIABLE IDENTIFICATION ON THE ESSENTIAL ARITY OF FUNCTIONS ON FINITE SETS

DOI10.1142/S012905410700508XzbMath1202.08001arXivmath/0701332MaRDI QIDQ3065611

Erkko Lehtonen, Miguel Couceiro

Publication date: 6 January 2011

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0701332

zbMATH Keywords

Boolean functions; arity gap; minors of functions; essential variables; functions on finite sets; variable identification

Mathematics Subject Classification ID

06E30: Boolean functions

08A40: Operations and polynomials in algebraic structures, primal algebras

Related Items

ADDITIVE DECOMPOSABILITY OF FUNCTIONS OVER ABELIAN GROUPS, A complete classification of equational classes of threshold functions included in clones, The arity gap of order-preserving functions and extensions of pseudo-Boolean functions, Join-irreducible Boolean functions, Decompositions of functions based on arity gap, Generalizations of Świerczkowski's lemma and the arity gap of finite functions, Parametrized arity gap

Cites Work

• Descending chains and antichains of the unary, linear, and monotone subfunction relations
• On the dependence of functions on their variables
• The forbidden projections of unate functions
• Galois theory for minors of finite functions
• Essential variables in hypersubstitutions.
• Boolean minors
• Equational characterizations of Boolean function classes
• Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes