Decompositions of functions based on arity gap

DOI10.1016/J.DISC.2011.08.028zbMATH Open1230.08001arXiv1003.1294OpenAlexW2047460659MaRDI QIDQ658046FDOQ658046

Authors: Miguel Couceiro, Erkko Lehtonen, Tamás Waldhauser 

Publication date: 11 January 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

arity gapdecomposition into sum of functionsfunctions of several variables

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• On the efficiency of normal form systems for representing Boolean functions
• The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
• Decompositions of functions based on arity gap
• Generalizations of Świerczkowski's lemma and the arity gap of finite functions
• Splittability ofp-ary functions
• Parametrized arity gap
• On finite functions with non-trivial arity gap
• Algebras, Graphs and Ordered Sets – ALGOS 2020 & the Mathematical Contributions of Maurice Pouzet
• ADDITIVE DECOMPOSABILITY OF FUNCTIONS OVER ABELIAN GROUPS
• Iteration-free decomposition of strongly dependent 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)