On a quasi-ordering on Boolean functions
| dc.creator | Couceiro, Miguel | |
| dc.creator | Pouzet, Maurice | |
| dc.date | 2006-01-10 | |
| dc.date.accessioned | 2026-07-07T06:58:43Z | |
| dc.date.available | 2026-07-07T06:58:43Z | |
| dc.description | It was proved few years ago that classes of Boolean functions definable by means of functional equations \cite{EFHH}, or equivalently, by means of relational constraints \cite{Pi2}, coincide with initial segments of the quasi-ordered set $(Ω, \leq)$ made of the set $Ω$ of Boolean functions, suitably quasi-ordered. The resulting ordered set $(Ω/\equiv, \sqsubseteq)$ embeds into $([ω]^{<ω}, \subseteq)$, the set -ordered by inclusion- of finite subsets of the set $ω$ of integers. We prove that $(Ω/\equiv, \sqsubseteq)$ also embeds $([ω]^{<ω}, \subseteq)$. We prove that initial segments of $(Ω, \leq)$ which are definable by finitely many obstructions coincide with classes defined by finitely many equations. This gives, in particular, that the classes of Boolean functions with a bounded number of essential variables are finitely definable. As an example, we provide a concrete characterization of the subclasses made of linear functions. | |
| dc.description | 14 pages | |
| dc.identifier | https://arxiv.org/abs/math/0601218 | |
| dc.identifier | http://arxiv.org/abs/math/0601218 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/107471 | |
| dc.subject | Combinatorics | |
| dc.subject | 06E30; 06A06 | |
| dc.title | On a quasi-ordering on Boolean functions | |
| dc.type | text |