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

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

Hypomorphic Sperner systems and non-reconstructible functions

in Order (2014)

A reconstruction problem is formulated for Sperner systems, and infinite families of non-reconstructible Sperner systems are presented. This has an application to a reconstruction problem for functions of ... [more ▼]

A reconstruction problem is formulated for Sperner systems, and infinite families of non-reconstructible Sperner systems are presented. This has an application to a reconstruction problem for functions of several arguments and identification minors. Sperner systems being representations of certain monotone functions, infinite families of non-reconstructible functions are thus obtained. The clones of Boolean functions are completely classified in regard to reconstructibility. [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 ▲]

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

E-print/Working paper (2013)

The class of threshold functions is known to be characterizable by functional equations or, equivalently, by pairs of relations, which are called relational constraints. It was shown by Hellerstein that ... [more ▼]

The class of threshold functions is known to be characterizable by functional equations or, equivalently, by pairs of relations, which are called relational constraints. It was shown by Hellerstein that this class cannot be characterized by a finite number of such objects. In this paper, we investigate classes of threshold functions which arise as intersections of the class of all threshold functions with clones of Boolean functions, and provide a complete classification of such intersections in respect to whether they have finite characterizations. Moreover, we provide a characterizing set of relational constraints for each class of threshold functions arising in this way. [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 Sheffer-criterion for partial 4-valued logic

in Journal of Multiple-Valued Logic & Soft Computing (2012), 18(2), 167-199

We determine the minimal covering of maximal partial clones in 4-valued logic. That means a necessary and sufficient condition for partial Sheffer functions in 4-valued logic in terms of the maximal ... [more ▼]

We determine the minimal covering of maximal partial clones in 4-valued logic. That means a necessary and sufficient condition for partial Sheffer functions in 4-valued logic in terms of the maximal partial clones is established. Furthermore several statements about members of the minimal covering of the maximal partial clones for any finite-valued logic are established. [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 ▲]

Galois theory for partial clones and some relational clones

in Proceedings - 41st IEEE International Symposium on Multiple-Valued Logic, ISMVL 2011 (2011)

A Galois connection between partial clones and a new variant of relation algebras is established. We introduce a new elementary operation on relations which captures the difference between total and ... [more ▼]

A Galois connection between partial clones and a new variant of relation algebras is established. We introduce a new elementary operation on relations which captures the difference between total and partial clones and allows us to adapt the proof of the Galois connection from the total case to the partial case. This Galois connection is able to capture all partial clones and is not restricted to strong partial clones as in previous work. [less ▲]