Decompositions of functions based on arity gap

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Jan 2012Embargo end date: 01 Jan 2010 France, Luxembourg, Hungary English Publisher:Elsevier BVJournal:Discrete Mathematics, volume 312, pages 238-247 (issn: 0012-365X,

Copyright policy )

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

doi: 10.1016/j.disc.2011.08.028 , 10.48550/arxiv.1003.1294

arXiv: 1003.1294

Decompositions of functions based on arity gap

- Summary
- Subjects
- Metrics

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

Countries

France, Luxembourg, Hungary

Related Organizations

Keywords

08A40, Variable identification minor, Operations and polynomials in algebraic structures, primal algebras, Physique, chimie, mathématiques & sciences de la terre, variable identification minor, Algèbre, 512, arity gap, 004, Theoretical Computer Science, Mathématiques, Physical, chemical, mathematical & earth Sciences, Boolean group, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Arity gap, decomposition into sum of functions, Combinatorics (math.CO), Mathematics, functions of several variables

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	6
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%