Show simple item record

dc.contributor.authorPouzet, Maurice
dc.contributor.authorCouceiro, Miguel
dc.date.accessioned2012-09-27T07:55:34Z
dc.date.available2012-09-27T07:55:34Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/10248
dc.language.isoenen
dc.subjectLinear functionsen
dc.subjectRelational constraintsen
dc.subjectEquational classesen
dc.subjectFunctional equationsen
dc.subjectEssential variablesen
dc.subjectMinorsen
dc.subjectBoolean functionsen
dc.subjectOrder-embeddingsen
dc.subjectAntichainsen
dc.subjectInitial segmentsen
dc.subjectPosetsen
dc.subjectPartial-ordersen
dc.subjectQosetsen
dc.subjectQuasi-ordersen
dc.subject.ddc3en
dc.titleOn a quasi-ordering on Boolean functionsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDépartement de Mathématiques, Université de Lyon I;France
dc.description.abstractenIt was proved few years ago that classes of Boolean functions definable by means of functional equations [O. Ekin, S. Foldes, P.L. Hammer, L. Hellerstein, Equational characterizations of boolean functions classes, Discrete Mathematics 211 (2000) 27–51], or equivalently, by means of relational constraints [N. Pippenger. Galois theory for minors of finite functions, Discrete Mathematics 254 (2002) 405–419], coincide with initial segments of the quasi-ordered set (Ω,≤) made of the set Ω of Boolean functions, suitably quasi-ordered. Furthermore, the classes defined by finitely many equations [O. Ekin, S. Foldes, P.L. Hammer, L. Hellerstein, Equational characterizations of boolean functions classes, Discrete Mathematics 211 (2000) 27–51] coincide with the initial segments of (Ω,≤) which are definable by finitely many obstructions. The resulting ordered set View the MathML source embeds into ([ω]<ω,⊆), the set–ordered by inclusion–of finite subsets of the set ω of integers. We prove that View the MathML source also embeds ([ω]<ω,⊆). From this result, we deduce that the dual space of the distributive lattice made of finitely definable classes is uncountable. Looking at examples of finitely definable classes, we show that the classes of Boolean functions with a bounded number of essential variables are finitely definable. We provide a concrete equational characterization for each of these classes, and for the subclasses made of linear functions. We describe the classes of functions with bounded polynomial degree in terms of minimal obstructions.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol396en
dc.relation.isversionofjnlissue1-3en
dc.relation.isversionofjnldate2008-05
dc.relation.isversionofjnlpages71–87en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2008.01.025en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
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