Show simple item record

Decompositions of functions based on arity gap

dc.contributor.authorWaldhauser, Tamás
dc.contributor.authorLehtonen, Erkko
HAL ID: 737805
ORCID: 0000-0002-9255-5876
dc.contributor.authorCouceiro, Miguel
HAL ID: 1498
dc.date.accessioned2012-09-26T14:43:07Z
dc.date.available2012-09-26T14:43:07Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/10244
dc.language.isoenen
dc.subjectArity gapen
dc.subjectvariable identification minoren
dc.subjectBoolean groupen
dc.subject.ddc512en
dc.titleDecompositions of functions based on arity gapen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversity of Szeged;
dc.contributor.editoruniversityotherUniversite du Luxembourg;
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameDiscrete Mathematics
dc.relation.isversionofjnlvol312en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages238-247en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.disc.2011.08.028en
dc.identifier.urlsitehttp://arxiv.org/abs/1003.1294en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelAlgèbreen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record