dc.contributor.author Lehtonen, Erkko HAL ID: 737805 ORCID: 0000-0002-9255-5876 dc.contributor.author Couceiro, Miguel HAL ID: 1498 dc.date.accessioned 2012-09-26T07:56:11Z dc.date.available 2012-09-26T07:56:11Z dc.date.issued 2009 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/10183 dc.language.iso en en dc.subject Semiprojection en dc.subject Arity gap en dc.subject Essential variables en dc.subject Variable identification minors en dc.subject Variable substitution en dc.subject Pseudo-Boolean functions en dc.subject Boolean functions en dc.subject Finite functions en dc.subject.ddc 515 en dc.title Generalizations of Swierczkowski’s lemma and the arity gap of finite functions en dc.type Article accepté pour publication ou publié dc.contributor.editoruniversityother Universite 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.isversionofjnlname Discrete Mathematics dc.relation.isversionofjnlvol 309 en dc.relation.isversionofjnlissue 20 en dc.relation.isversionofjnldate 2009 dc.relation.isversionofjnlpages 5905-5912 en dc.relation.isversionofdoi http://dx.doi.org/10.1016/j.disc.2009.04.009 en dc.identifier.urlsite http://arxiv.org/abs/0712.1753 dc.relation.isversionofjnlpublisher Elsevier en dc.subject.ddclabel Analyse en dc.relation.forthcoming non en dc.relation.forthcomingprint non en
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.