Decompositions of functions based on arity gap
Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel (2012), Decompositions of functions based on arity gap, Discrete Mathematics, 312, 2, p. 238-247. http://dx.doi.org/10.1016/j.disc.2011.08.028
Type
Article accepté pour publication ou publiéExternal document link
http://arxiv.org/abs/1003.1294Date
2012Journal name
Discrete MathematicsVolume
312Number
2Publisher
Elsevier
Pages
238-247
Publication identifier
Metadata
Show full item recordAbstract (EN)
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.Subjects / Keywords
Arity gap; variable identification minor; Boolean groupRelated items
Showing items related by title and author.
-
Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel (2012) Article accepté pour publication ou publié
-
Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel (2013) Article accepté pour publication ou publié
-
Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel (2015) Article accepté pour publication ou publié
-
Couceiro, Miguel; Lehtonen, Erkko; Waldhauser, Tamás (2014) Article accepté pour publication ou publié
-
Lehtonen, Erkko; Couceiro, Miguel; Couceiro, Miguel (2008) Communication / Conférence