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
2008Journal name
Theoretical Computer ScienceVolume
396Number
1-3Publisher
Elsevier
Pages
71–87
Publication identifier
Metadata
Show full item recordAbstract (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-ordersRelated items
Showing items related by title and author.
-
Pouzet, Maurice; Couceiro, Miguel (2006) Communication / Conférence
-
Bouaziz, Moncef; Pouzet, Maurice; Couceiro, Miguel (2010) Article accepté pour publication ou publié
-
Marichal, Jean-Luc; Couceiro, Miguel (2011) Article accepté pour publication ou publié
-
Waldhauser, Tamás; Marichal, Jean-Luc; Couceiro, Miguel (2012) Article accepté pour publication ou publié
-
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