Show simple item record

dc.contributor.authorLehtonen, Erkko
dc.contributor.authorCouceiro, Miguel
dc.date.accessioned2012-09-26T07:56:11Z
dc.date.available2012-09-26T07:56:11Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/10183
dc.language.isoenen
dc.subjectSemiprojectionen
dc.subjectArity gapen
dc.subjectEssential variablesen
dc.subjectVariable identification minorsen
dc.subjectVariable substitutionen
dc.subjectPseudo-Boolean functionsen
dc.subjectBoolean functionsen
dc.subjectFinite functionsen
dc.subject.ddc515en
dc.titleGeneralizations of Swierczkowski’s lemma and the arity gap of finite functionsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversite du Luxembourg;
dc.description.abstractenŚwierczkowski’s lemma–as it is usually formulated–asserts that if f:An→A is an operation on a finite set A, n≥4, and every operation obtained from f by identifying a pair of variables is a projection, then f is a semiprojection. We generalize this lemma in various ways. First, it is extended to B-valued functions on A instead of operations on A and to essentially at most unary functions instead of projections. Then we characterize the arity gap of functions of small arities in terms of quasi-arity, which in turn provides a further generalization of Świerczkowski’s lemma. Moreover, we explicitly classify all pseudo-Boolean functions according to their arity gap. Finally, we present a general characterization of the arity gaps of B-valued functions on arbitrary finite sets A.en
dc.relation.isversionofjnlnameDiscrete Mathematics
dc.relation.isversionofjnlvol309en
dc.relation.isversionofjnlissue20en
dc.relation.isversionofjnldate2009
dc.relation.isversionofjnlpages5905-5912en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.disc.2009.04.009en
dc.identifier.urlsitehttp://arxiv.org/abs/0712.1753
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelAnalyseen
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