Dichotomy on intervals of strong partial Boolean clones

in Algebra Universalis (2015), 73(3), 347-368

The following result has been shown recently in the form of a dichotomy: For every total clone $C$ on $\2 := \{0,1\}$, the set $\intervalD{C}$ of all partial clones on $\2$ whose total component is $C ... [more ▼]

The following result has been shown recently in the form of a dichotomy: For every total clone $C$ on $\2 := \{0,1\}$, the set $\intervalD{C}$ of all partial clones on $\2$ whose total component is $C$, is either finite or of continuum cardinality. In this paper we show that the dichotomy holds, even if only strong partial clones are considered, i.e., partial clones which are closed under taking subfunctions: For every total clone $C$ on $\2$, the set $\intervalStr{C}$ of all strong partial clones on $\2$ whose total component is $C$, is either finite or of continuum cardinality. [less ▲]

A complete classification of equational classes of threshold functions included in clones

in RAIRO : Operations Research = Recherche Opérationnelle (2015), 49(1), 3966

Relation graphs and partial clones on a 2-element set.

in Multiple-Valued Logic (ISMVL), 2014 IEEE 44rd International Symposium on (2014)

In a recent paper, the authors show that the sublattice of partial clones that preserve the relation $\{(0,0),(0,1),(1,0)\}$ is of continuum cardinality on $\2$. In this paper we give an alternative proof ... [more ▼]

In a recent paper, the authors show that the sublattice of partial clones that preserve the relation $\{(0,0),(0,1),(1,0)\}$ is of continuum cardinality on $\2$. In this paper we give an alternative proof to this result by making use of a representation of relations derived from $\{(0,0),(0,1),(1,0)\}$ in terms of certain types of graphs. As a by-product, this tool brings some light into the understanding of the structure of this uncountable sublattice of strong partial clones. [less ▲]

Intervals of the homomorphism order of graphs have infinite width

E-print/Working paper (2014)

The homomorphism order of graphs is known to be dense with a single exception. We strengthen this result by showing that, with this single exception, the interval between any two distinct comparable ... [more ▼]

The homomorphism order of graphs is known to be dense with a single exception. We strengthen this result by showing that, with this single exception, the interval between any two distinct comparable graphs includes an infinite antichain. Moreover, every antichain included in such an interval can be extended into an infinite one within that interval. [less ▲]

Sur des classes de fonctions à seuil caractérisables par des contraintes relationnelles

in Marichal, Jean-Luc; Essounbouli, Najib; Guelton, Kevin (Eds.) Actes des 22èmes rencontres francophones sur la Logique Floue et ses Applications, 10-11 octobre 2013, Reims, France (2013, October)

Motivated by modal semantics induced by majority games, we consider the class of threshold functions. It was shown by L. Hellerstein that this class is characterizable by relational constraints (or ... [more ▼]

Motivated by modal semantics induced by majority games, we consider the class of threshold functions. It was shown by L. Hellerstein that this class is characterizable by relational constraints (or equivalently, by functional equations), but that there is no characterization by means of finitely many constraints. In this paper, we present a complete classification of classes of threshold functions induced by Boolean clones, into whether they are characterizable by finitely many relational constraints. Moreover we provide sets of constraints characterizing each of such classes. [less ▲]

Set-reconstructibility of Post classes

E-print/Working paper (2013)

The clones of Boolean functions are classified in regard to set-reconstructibility via a strong dichotomy result: the clones containing only affine functions, conjunctions, disjunctions or constant ... [more ▼]

The clones of Boolean functions are classified in regard to set-reconstructibility via a strong dichotomy result: the clones containing only affine functions, conjunctions, disjunctions or constant functions are set-reconstructible, whereas the remaing clones are not weakly reconstructible. [less ▲]

A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones

in Multiple-Valued Logic (ISMVL), 2013 IEEE 43rd International Symposium on (2013)

The following natural problem, first considered by D. Lau, has been tackled by several authors recently: Let C be a total clone on 2 := {0, 1}. Describe the interval I(C) of all partial clones on 2 whose ... [more ▼]

The following natural problem, first considered by D. Lau, has been tackled by several authors recently: Let C be a total clone on 2 := {0, 1}. Describe the interval I(C) of all partial clones on 2 whose total component is C. We establish some results in this direction and combine them with previous ones to show the following dichotomy result: For every total clone C on 2, the set I(C) is either finite or of continuum cardinality. [less ▲]

Counting the maximal partial clones on a finite set

in Journal of Multiple-Valued Logic and Soft Computing (2012), 18(2), 153-165

We show that different coherent relations specify different maximal partial clones. Then we describe a computer program to find all coherent relations and thus all maximal partial clones on 4-element, 5 ... [more ▼]

We show that different coherent relations specify different maximal partial clones. Then we describe a computer program to find all coherent relations and thus all maximal partial clones on 4-element, 5-element, and 6-element sets. [less ▲]

A generalization of Completely Separating Systems

in Discrete Mathematics (2012), 312(22), 3213-3227

A Completely Separating System (CSS) C on [n] is a collection of blocks of [n] such that for any pair of distinct points x,y ∈ [n], there exist blocks A,B ∈ C such that x ∈ A-B and y ∈ B-A. One possible ... [more ▼]

A Completely Separating System (CSS) C on [n] is a collection of blocks of [n] such that for any pair of distinct points x,y ∈ [n], there exist blocks A,B ∈ C such that x ∈ A-B and y ∈ B-A. One possible generalization of CSSs are r-CSSs. Let T be a subset of 2[n], the power set of [n]. A point i ∈ [n] is called r-separable if for every r-subset S ⊆ [n]-i there exists a block T ∈ T with i ∈ T and with the property that S is disjoint from T. If every point i ∈ [n] is r-separable, then T is an r-CSS (or r-(n)CSS). Furthermore, if T is a collection of k-blocks, then T is an r-(n,k)CSS. In this paper we offer some general results, analyze especially the case r=2 with the additional condition that k ≥ 5, present a construction using Latin squares, and mention some open problems. © 2012 Elsevier B.V. All rights reserved. [less ▲]

Uniqueness of minimal coverings of maximal partial clones

in Algebra Universalis (2011), 65(4), 393-420

A partial function f on a k-element set Ek is a partial Sheffer function if every partial function on Ek is definable in terms of f. Since this holds if and only if f belongs to no maximal partial clone ... [more ▼]

A partial function f on a k-element set Ek is a partial Sheffer function if every partial function on Ek is definable in terms of f. Since this holds if and only if f belongs to no maximal partial clone on Ek, a characterization of partial Sheffer functions reduces to finding families of minimal coverings of maximal partial clones on Ek. We show that for each k ≥ 2, there exists a unique minimal covering. [less ▲]