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

DOI10.1142/S012905410700508XzbMATH Open1202.08001arXivmath/0701332MaRDI QIDQ3065611FDOQ3065611

Authors: Miguel Couceiro, Erkko Lehtonen 

Publication date: 6 January 2011

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

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.

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

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

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)

Cites Work

• Galois theory for minors of finite functions
• The forbidden projections of unate functions
• Boolean minors
• Equational characterizations of Boolean function classes
• 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
• Essential variables in hypersubstitutions.
• On the dependence of functions on their variables

Cited In (11)

• 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
• Content and singletons bring unique identification minors

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)