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

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

Miguel Couceiro, Erkko Lehtonen

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, Variants of Essential Arity for Partial Functions

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