Decompositions of functions based on arity gap

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.

13 pages

References in corpus (6)

• Generalizations of Swierczkowski's lemma and the arity gap of finite functions
• Equivalence of operations with respect to discriminator clones
• On the lattice of equational classes of Boolean functions and its closed intervals
• On the effect of variable identification on the essential arity of functions
• On the arity gap of polynomial functions
• On finite functions with non-trivial arity gap

Cited by in corpus (3)

• The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
• On the arity gap of polynomial functions
• Additive decomposability of functions over abelian groups