• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

On a quasi-ordering on Boolean functions

Pouzet, Maurice; Couceiro, Miguel (2008), On a quasi-ordering on Boolean functions, Theoretical Computer Science, 396, 1-3, p. 71–87. http://dx.doi.org/10.1016/j.tcs.2008.01.025

Type
Article accepté pour publication ou publié
Date
2008
Journal name
Theoretical Computer Science
Volume
396
Number
1-3
Publisher
Elsevier
Pages
71–87
Publication identifier
http://dx.doi.org/10.1016/j.tcs.2008.01.025
Metadata
Show full item record
Author(s)
Pouzet, Maurice
Couceiro, Miguel
Abstract (EN)
It 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.
Subjects / Keywords
Linear functions; Relational constraints; Equational classes; Functional equations; Essential variables; Minors; Boolean functions; Order-embeddings; Antichains; Initial segments; Posets; Partial-orders; Qosets; Quasi-orders

Related items

Showing items related by title and author.

  • Thumbnail
    Equational definability and a quasi-order on Boolean functions 
    Pouzet, Maurice; Couceiro, Miguel (2006) Communication / Conférence
  • Thumbnail
    Join-irreducible Boolean functions 
    Bouaziz, Moncef; Pouzet, Maurice; Couceiro, Miguel (2010) Article accepté pour publication ou publié
  • Thumbnail
    Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions 
    Marichal, Jean-Luc; Couceiro, Miguel (2011) Article accepté pour publication ou publié
  • Thumbnail
    Locally monotone Boolean and pseudo-Boolean functions 
    Waldhauser, Tamás; Marichal, Jean-Luc; Couceiro, Miguel (2012) Article accepté pour publication ou publié
  • Thumbnail
    Hierarchies of local monotonicities and lattice derivatives for Boolean and pseudo-Boolean functions 
    Waldhauser, Tamás; Marichal, Jean-Luc; Couceiro, Miguel (2012) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo