On the effect of variable identification on the essential arity of functions on finite sets

DOI10.1142/S012905410700508XMaRDI QIDQ3065611zbMATH OpenFDO

Authors 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 functionsarity gapminors of functionsessential variablesfunctions on finite setsvariable identification

Mathematics Subject Classification ID

Boolean functions (06E30) Operations and polynomials in algebraic structures, primal algebras (08A40)

Abstract: We show that every function of several variables on a finite set of k elements with n>k essential variables has a variable identification minor with at least n-k essential variables. This is a generalization of a theorem of Salomaa on the essential variables of Boolean functions. We also strengthen Salomaa's theorem by characterizing all the Boolean functions f having a variable identification minor that has just one essential variable less than f.

Recommendations

• Essential arity gap of Boolean functions
• On the arity gap of finite functions: results and applications
• scientific article; zbMATH DE number 4218111
• On finite functions with non-trivial arity gap
• scientific article; zbMATH DE number 1867110

Cites work

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

Cited in

(11)

• Content and singletons bring unique identification minors
• The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
• Join-irreducible Boolean functions
• Decompositions of functions based on arity gap
• Additive decomposability of functions over abelian groups
• Generalizations of Świerczkowski's lemma and the arity gap of finite functions
• A complete classification of equational classes of threshold functions included in clones
• From infinite to finite by identifying variables in many-valued logic
• Parametrized arity gap
• Variants of Essential Arity for Partial Functions
• Functions essentially depending on at most one variable

This page was built for publication: On the effect of variable identification on the essential arity of functions on finite sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3065611)