Show simple item record

On the arity gap of finite functions: results and applications

dc.contributor.authorCouceiro, Miguel
HAL ID: 1498
dc.contributor.authorLehtonen, Erkko
HAL ID: 737805
ORCID: 0000-0002-9255-5876
dc.date.accessioned2012-09-28T07:53:55Z
dc.date.available2012-09-28T07:53:55Z
dc.date.issued2016
dc.identifier.issn1542-3980
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/10321
dc.language.isoenen
dc.subjectvariable substitution
dc.subjectBoolean function
dc.subjectessential variable
dc.subjectarity gap
dc.subjectFinite function
dc.subject.ddc512en
dc.titleOn the arity gap of finite functions: results and applications
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversite du Luxembourg;
dc.description.abstractenLet A be a finite set and B an arbitrary set with at least two elements. The arity gap of a function f:An→B is the minimum decrease in the number of essential variables when essential variables of f are identified. A non-trivial fact is that the arity gap of such B-valued functions on A is at most |A|. Even less trivial to verify is the fact that the arity gap of B-valued functions on A with more than |A| essential variables is at most 2. These facts ask for a classification of B-valued functions on A in terms of their arity gap. In this paper, we survey what is known about this problem. We present a general characterization of the arity gap of B-valued functions on A and provide explicit classifications of the arity gap of Boolean and pseudo-Boolean functions. Moreover, we reveal unsettled questions related to this topic, and discuss links and possible applications of some results to other subjects of research.
dc.relation.isversionofjnlnameJournal of Multiple-Valued Logic and Soft Computing
dc.relation.isversionofjnlvol27
dc.relation.isversionofjnlissue2-3
dc.relation.isversionofjnldate2016
dc.relation.isversionofjnlpages193-207
dc.relation.isversionofjnlpublisherOCP Science
dc.subject.ddclabelAlgèbreen
dc.relation.forthcomingouien
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewednon
dc.date.updated2016-12-03T15:57:04Z


Files in this item

Thumbnail
Name:
ROGICS08-CL.pdf
Size:
170.4Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record