Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Power series solutions of Tarski's associativity law and of the cyclic associativity law Schölzel, Karsten ; Tomaschek, Jörg in Aequationes Mathematicae (2016), 90(2), 411425 Detailed reference viewed: 91 (3 UL)Dichotomy on intervals of strong partial Boolean clones Schölzel, Karsten 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 ▲] Detailed reference viewed: 128 (15 UL)A complete classification of equational classes of threshold functions included in clones Couceiro, Miguel ; Lehtonen, Erkko ; Schölzel, Karsten in RAIRO: Recherche Opérationnelle (2015), 49(1), 3966 Detailed reference viewed: 121 (10 UL)Set-reconstructibility of Post classes Couceiro, Miguel ; Lehtonen, Erkko ; Schölzel, Karsten in Discrete Applied Mathematics (2015), 187 Detailed reference viewed: 101 (5 UL)Partial R-clones Schölzel, Karsten ; 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 ▲] Detailed reference viewed: 41 (1 UL)Relation graphs and partial clones on a 2-element set. Schölzel, Karsten ; ; et al 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 ▲] Detailed reference viewed: 94 (3 UL)Intervals of the homomorphism order of graphs have infinite width ; Schölzel, Karsten 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 ▲] Detailed reference viewed: 46 (3 UL)Hypomorphic Sperner systems and non-reconstructible functions Couceiro, Miguel ; Lehtonen, Erkko ; Schölzel, Karsten in Order: A Journal on the Theory of Ordered Sets and its Applications (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 ▲] Detailed reference viewed: 143 (29 UL)Countable intervals of partial clones ; Schölzel, Karsten in Multiple-Valued Logic (ISMVL), 2014 IEEE 44rd International Symposium on (2014) Let $k \ge 2$ and $A$ be a $k$-element set. We construct countably infinite unrefinable chains of strong partial clones on $A$. This provides the first known examples of countably infinite intervals of ... [more ▼] Let $k \ge 2$ and $A$ be a $k$-element set. We construct countably infinite unrefinable chains of strong partial clones on $A$. This provides the first known examples of countably infinite intervals of strong partial clones on a finite set with at least two elements. [less ▲] Detailed reference viewed: 98 (1 UL)Sur des classes de fonctions à seuil caractérisables par des contraintes relationnelles ; Lehtonen, Erkko ; Schölzel, Karsten 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 ▲] Detailed reference viewed: 168 (1 UL)Intersections with Slupecki Partial Clones on a Finite Set Schölzel, Karsten ; in Multiple-Valued Logic (ISMVL), 2013 IEEE 43rd International Symposium on (2013, May) We study intersections of partial clones on the k-element set with k ≥ 2. More precisely we consider intersections of Slupecki partial clones with non-Slupecki maximal partial clones on k. Detailed reference viewed: 104 (3 UL)Upside down with the strong partial clones Schölzel, Karsten E-print/Working paper (2013) Detailed reference viewed: 44 (5 UL)A complete classification of equational classes of threshold functions included in clones ; Lehtonen, Erkko ; Schölzel, Karsten 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 ▲] Detailed reference viewed: 101 (3 UL)A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones Schölzel, Karsten ; Couceiro, Miguel ; et al 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 ▲] Detailed reference viewed: 103 (2 UL)Set-reconstructibility of Post classes ; Lehtonen, Erkko ; Schölzel, Karsten 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 ▲] Detailed reference viewed: 86 (3 UL)A Sheffer-criterion for partial 4-valued logic Schölzel, Karsten in Journal of Multiple-Valued Logic and 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 ▲] Detailed reference viewed: 67 (2 UL)A generalization of Completely Separating Systems ; Schölzel, Karsten 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 ▲] Detailed reference viewed: 86 (0 UL)Counting the maximal partial clones on a finite set Schölzel, Karsten 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 ▲] Detailed reference viewed: 45 (2 UL)Uniqueness of minimal coverings of maximal partial clones Schölzel, Karsten 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 ▲] Detailed reference viewed: 90 (0 UL)Galois theory for partial clones and some relational clones Schölzel, Karsten 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 ▲] Detailed reference viewed: 80 (0 UL) |
||