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 ▲]

Set-reconstructibility of Post classes

in Discrete Applied Mathematics (2015), 187

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 ▲]

Partial R-clones

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

In [Romov, ISMVL 2013] the first author introduced a type of partial clones as the intersection of some special infinite descending chains similar to I. Rosenberg (1972) in the case of total clones. We ... [more ▼]

In [Romov, ISMVL 2013] the first author introduced a type of partial clones as the intersection of some special infinite descending chains similar to I. Rosenberg (1972) in the case of total clones. We provide a characterization of these clones in terms of their invariants, and propose a generalization of such clones, which we will call partial R-clones. We show that there are only finitely many partial R-clones. Furthermore, we investigate some properties related to their position in the lattice of partial clones. [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 ▲]

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 ▲]

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 ▲]

Clones of partial functions on finite sets.

Book published by Aachen: Shaker Verlag; Rostock: Univ. Rostock, Mathematisch-Naturwissenschaftliche Fakultät (Diss. 2010) (2011)