Typed Semigroups, Majority Logic, and Threshold Circuits

Abstract

In this thesis we focused on the interplay of logic, algebra and circuit theory. While their interaction was previously mainly studied for the case of regular languages we extend the focus to non-regular languages and show that similar connections can be proven. One of the big open questions in circuit theory is whether the classes TC0 and NC1 coincide, which is equivalent to the question whether L_A5 in TC0. In this thesis we established some separation results for subclasses of TC0 that might finally result in a separation of TC0 from NC1.

We started by giving an algebraic characterization for arbitrary logic and circuit classes. Of course, any such characterization includes non-regular languages and hence finite semigroups are not sufficient, whereas infinite semigroups are too cumbersome. The key ingredient to this characterization was the typed semigroup which allowed for infinite semigroups, taming them by additional algebraic structures. The theory of typed semigroups coincides with the theory of finite semigroups in the finite case, additionally allowing for finer correspondences, and is a natural extension for the infinite case.

The known connections between algebra, logic and circuits were extended in a unifying proof. For this we needed to extend the block product to typed semigroups. One must exercise caution when defining the block product for an infinite structure, since the power of an infinite object is hard to handle. Using the block product principle extended to the infinite case, and to unbounded variables in logic as well, we gave a full picture of the connections between logic, circuits and algebra. It should be noted that this proof covers all known connections in the finite case in a much more general way.

Examining restrictions like two variables, the relations between two variable logic, weakly blocked semigroups and linear size circuits, were also generalized to arbitrary quantifiers and to arbitrary predicates using weakly blocked typed semigroups. In this case, too, the known proofs for these connections were entirely covered by our proof.

Therefore this paper gave an algebraic characterization for any class of logic in terms of typed semigroups. Having found this characterization we can also easily see when an algebraic characterization in terms of finite semigroups exists for a given class of logic. On the algebraic side restrictions like a bounded number of variables or a bounded quantifier depth can also be modeled.

Having found this algebraic characterization we apply it to the case of majority logic or threshold circuits. The superordinate goal is to separate TC0 from NC1. Since a lot of effort was put into this by other researchers with limited success, e.g. TC0 is still not separated from NP, it is not surprising that we do not accomplish a separation of TC0 from NC1. So we restrict ourselves to the subclass of MAJ[<] logic with only two variables.

Using the algebraic characterization via typed semigroup for this class of logic, which is basically a direct product of the integers that can be blocked weakly, we embed it into the Euclidean space. We then show by geometric means how to describe which words can be separated by a majority formula of depth one. It transpires that there is a correspondence between these formulas and hyperplanes in the vector space. It is intuitively obvious that with a constant number of hyperplanes an arbitrarily large cube cannot be split in such a way that all integer valued points are separated. Translated back to our logic this gives us two words, having the same truth value for all formulas of depth one.

Using induction we can give an upper bound on the power of EMAJ[<] formulas with two variables. Using geometric intuition there seem to be many possible extensions, but in order to give clean proofs we will formalize them using algebra. Our algebraic concept allows us to enlarge the allowed quantifier set and predicate set to show that FO+MOD+EMAJ[reg,arbun] with two variables cannot recognize any language with a non-solvable syntactic semigroup.

The techniques introduced here differ completely from previous attempts, and it appears to be likely that they can be extended to bigger subclasses of TC0 or even TC0. We touch on some possible ways of extending the given proofs in the end of the chapters, and will now finalize this thesis by motivating some other open questions that could lead to a separation of TC0 and NC1 or at least from NP.

Mit der Definition der getypten Halbgruppen wird die Grenze von regulären Sprachen und endlichen Halbgruppen überschritten. Es wird gezeigt, dass die getypten Halbgruppen auf natürliche Weise eine Kategorie bilden, und das Varietätentheorem von Eilenberg für die Kategorie erweitert wird.

Um besser auf einige Details von getypten Halbgruppen eingehen zu können, wird die übliche Situation beim Erkennen von Sprachen per Homomorphismus genau aufgezeigt: Sei L eine formale Sprache über dem Alphabet Sigma und (S,S,E) die syntaktische Halbgruppe. Folglich gibt es einen syntaktischen Morphismus h von Sigma^+ nach (S,S,E) und eine Teilmenge A, so dass sich die Sprache als Urbild von dieser Menge schreiben läßt: L=h^-1(A). Es gibt also neben der syntaktischen Halbgruppe noch weitere algebraische Objekte, die die Sprache beschreiben: den Homomorphismus h und die akzeptierende Menge A. Diese beide Objekte werden in die Definition von getypten Halbgruppen einfließen.

Eine getypte Halbgruppe besteht aus einem Tripel: einer Halbgruppe, einer Booleschen Algebra über der Halbgruppe, und einer Menge von Einheiten. Die Typen sind die Elemente der Boolesche Algebra und werden verwendet, um die akzeptierenden Teilmengen einzuschränken, während die Menge der Einheiten verwendet wird, um einen Längenbegriff auf den getypten Halbgruppen zu erhalten.

Um eine strukturelle Beziehung zwischen Logik und den getypten Halbgruppen herzustellen, wird das Block Produkt für getypte Halbgruppen verallgemeinert. Dadurch kann für jede Logik, die durch eine Menge von Quantoren und eine Menge von Prädikaten definiert ist, eine algebraische Charakterisierung durch getypte Halbgruppen angeben werden. Dazu wird das Block Produkt Prinzip, das im endlichen Fall für Logik mit zwei Variablen verwendet wurde, auf unendliche Halbgruppen erweitert und erstmalig auch konsequent für den Fall von unbeschränkt vielen Variablen verwendet.

Für Schaltkreisklassen wird ein gleichartiges Resultat erzielt: Jede Schaltkreisklasse, die durch ihre Basis (=Gattertypen) und ihre Uniformität festgelegt ist, kann durch eine Klasse von getypten Halbgruppen charakterisiert werden. Um verbesserte Resultate zu erhalten, wird eine eigene Definition der Uniformitätssprache, die näher an der Logik orientiert ist, verwendet.