Decompositions of functions based on arity gap

DOI10.1016/J.DISC.2011.08.028zbMATH1230.08001OpenAlexW2047460659MaRDI QIDQ658046FDOQ658046

Authors Miguel Couceiro, Erkko Lehtonen, Tamás Waldhauser

Publication date 11 January 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

arity gapdecomposition into sum of functionsfunctions of several variables

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40)

Abstract: We study the arity gap of functions of several variables defined on an arbitrary set A and valued in another set B. The arity gap of such a function is the minimum decrease in the number of essential variables when variables are identified. We establish a complete classification of functions according to their arity gap, extending existing results for finite functions. This classification is refined when the codomain B has a group structure, by providing unique decompositions into sums of functions of a prescribed form. As an application of the unique decompositions, in the case of finite sets we count, for each n and p, the number of n-ary functions that depend on all of their variables and have arity gap p.

Recommendations

• On the arity gap of finite functions: results and applications
• On finite functions with non-trivial arity gap
• scientific article; zbMATH DE number 6930495
• Finite symmetric functions with non-trivial arity gap
• On separable sets in finite functions with non-trivial arity gap

Cites work

• scientific article; zbMATH DE number 3150816 (Why is no real title available?)
• scientific article; zbMATH DE number 4061235 (Why is no real title available?)
• scientific article; zbMATH DE number 3216991 (Why is no real title available?)
• scientific article; zbMATH DE number 3266649 (Why is no real title available?)
• scientific article; zbMATH DE number 3313256 (Why is no real title available?)
• Boolean minors
• Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
• Decompositions of functions based on arity gap
• Descending chains and antichains of the unary, linear, and monotone subfunction relations
• Equivalence of operations with respect to discriminator clones
• Essential arities of term operations in finite algebras
• Essential variables in hypersubstitutions.
• Galois theory for minors of finite functions
• Generalizations of Świerczkowski's lemma and the arity gap of finite functions
• On a quasi-ordering on Boolean functions
• On finite functions with non-trivial arity gap
• On the Number of Operations in a Clone
• On the effect of variable identification on the essential arity of functions on finite sets
• On the lattice of equational classes of Boolean functions and its closed intervals
• The forbidden projections of unate functions
• Two Theorems on Essential Variables

Cited in

(14)

• Iteration-free decomposition of strongly dependent functions
• Decompositions of functions based on arity gap
• Algebras, Graphs and Ordered Sets – ALGOS 2020 & the Mathematical Contributions of Maurice Pouzet
• Finite symmetric functions with non-trivial arity gap
• On the efficiency of normal form systems for representing Boolean functions
• On the arity gap of finite functions: results and applications
• Parametrized arity gap
• The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
• Additive decomposability of functions over abelian groups
• Additive decomposition schemes for polynomial functions over fields
• On separable sets in finite functions with non-trivial arity gap
• On finite functions with non-trivial arity gap
• Splittability ofp-ary functions
• Generalizations of Świerczkowski's lemma and the arity gap of finite functions

This page was built for publication: Decompositions of functions based on arity gap

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