Reference : Decompositions of functions based on arity gap
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/10993/3163
Decompositions of functions based on arity gap
English
Couceiro, Miguel mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]
Lehtonen, Erkko mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Waldhauser, Tamás mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]
2012
Discrete Mathematics
Elsevier
312
2
238-247
Yes (verified by ORBilu)
International
0012-365X
[en] arity gap ; variable identification minor ; Boolean group
[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 decomposition 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.
http://hdl.handle.net/10993/3163
10.1016/j.disc.2011.08.028

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
DecompositionsGap.pdfAuthor postprint304.58 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.