Browsing by Author "Diekert, Volker (Prof. Dr.)"

Now showing 1 - 13 of 13

Open Access
Algorithms and complexity results for finite semigroups
(2019) Fleischer, Lukas; Diekert, Volker (Prof. Dr.)
We consider the complexity of decision problems for regular languages given as recognizing morphisms to finite semigroups. We describe efficient algorithms for testing language emptiness, universality, inclusion, equivalence and finiteness, as well as intersection non-emptiness. Some of these algorithms have sublinear running time and are therefore implemented on random-access Turing machines or Boolean circuits. These algorithms are complemented by lower bounds. We give completeness results for the general case and also investigate restrictions to certain varieties of finite semigroups. Except for intersection non-emptiness, the problems mentioned above are shown to be closely connected to the Cayley semigroup membership problem, i.e., membership of an element to a subsemigroup given by a multiplication table and a set of generators. Therefore, the complexity of this problem is one of the main topics of this thesis. In many (but not all) cases, efficient algorithms for Cayley semigroup membership are based on the existence of succinct representations of semigroup elements over a given set of generators. These representations are algebraic circuits, also referred to as straight-line programs. As a compressibility measure for such representations within specific classes of finite semigroups, we introduce a framework called circuits properties. We give algebraic characterizations of certain classes of circuits properties and derive complexity results. As a byproduct, a generalization of a long-standing open problem in complexity theory is resolved. For intersection non-emptiness, a similar tool called product circuits properties is used. We provide completeness results for the problem of deciding membership to varieties of finite semigroups and to varieties of languages. We show that many varieties, which were previously known to be decidable in polynomial time, are actually in DLOGTIME-uniform AC^0. The key ingredient is definability of varieties by first-order formulas. Combining our results with known lower bounds for deciding Parity, we also present a novel technique to prove that a specific variety cannot be defined by first-order formulas with multiplication. Since such formulas are more expressive than finite sets of ω-identities, this implies non-definability by finite sets of ω-identities.
Open Access
Ambiguity functions of context-free grammars and languages
(2005) Wich, Klaus; Diekert, Volker (Prof. Dr.)
This thesis investigates the relationship between the ambiguity functions for context-free grammars and for context-free languages. It also examines which functions are ambiguity functions and how different ambiguity classes relate to each other. The results can be applied to generalise known results on sequential and parallel parsing of context-free grammars. To understand the main results we define some notions briefly: The ambiguity of a word with respect to a context-free grammar is the number of its derivation trees. The ambiguity function of a context-free grammar maps an integer n to the maximal ambiguity of a word whose length is bounded by n. A context-free language L is f-ambiguous if f is the ambiguity function of some context-free grammar generating L and, roughly speaking, no context-free grammar generating L has a substantially lower ambiguity. A function is an inherent ambiguity function if there is an f-ambiguous context-free language. A homomorphism which maps a symbol either to itself or to the empty word is called a projection. A symbol a is called bounded in a language L if there is a constant c such that no word in L has more than c occurrences of the symbol a. A projection is a bounded contraction for a language L if it erases only symbols which are bounded in L. The main results are: 1. The set of ambiguity functions for cycle-free context-free grammars and the set of inherent ambiguity functions coincide. 2. A technical statement which implies the following two facts: 2.1. The class of context-free languages with polynomially bounded ambiguity is the closure of the class of unambiguous context-free languages under bounded contractions. 2.2. Each reduced cycle-free context-free grammar G is either exponentially ambiguous or its ambiguity is bounded by a polynomial which can be computed from G. (2.2. was already part of the authors Diploma thesis, but the new proof yields in many cases a better polynomial (a polynomial with a lower degree), but never a worse polynomial.) 3. For each computable divergent total non-decreasing function f there is a divergent ambiguity function g such that g(n) is lower than or equal to f(n) for each positive integer n. In fact, the same ambiguity functions occur for the generation of rational trace languages over special independence alphabets. (A rational trace language T is generated by a regular (word) language R if T is the set of traces which are represented by the words in R. The ambiguity of a trace t is the number of representatives in R. It is now straightforward to define the ambiguity function for the generation of T by R.) In addition the thesis contains generalisations for known results on sequential and parallel parsing of context-free grammars. In particular, the thesis considers the (sequential) Earley parsing time of context-free grammars with sublinear ambiguity functions (known to exist due to result 3). Moreover it is shown that each reduced context-free grammars with a polynomially bounded ambiguity can be parsed in logarithmic time on a CREW-PRAM. This is an immediate consequence of 2.1. and a known result for the parallel parsing time of unambiguous context-free grammars.
Open Access
Automaton structures : decision problems and structure theory
(2020) Wächter, Jan Philipp; Diekert, Volker (Prof. Dr.)
This thesis is devoted to the class of automaton groups and semigroups, which has gained a reputation of containing groups and semigroups with special algebraic properties that are hard to find elsewhere. Both automaton groups and semigroups are studied from a structural and an algorithmic perspective. We motivate the use of partial automata as generating objects for algebraic structures and compare them to their complete counterparts. Additionally, we give further examples of semigroups that cannot be generated by finite automata and show that every inverse automaton semigroup is generated by a partial, invertible automaton. Moreover, we study the finite and infinite orbits of ω-words under the action induced by an automaton. Here, our main result is that every infinite automaton semigroup admits an ω-word with an infinite orbit. We apply these structural results algorithmically and show that the word problem for automaton groups and semigroups is PSpace-complete. Furthermore, we investigate a decision problem related to the freeness of automaton groups and semigroups: we show that it is undecidable whether a given automaton admits a non-trivial state sequences that acts trivially and we use this problem for further reductions. Afterwards, we strengthen Gillibert’s result on the undecidability of the finiteness problem for automaton semigroups and give a partial solution for the group case of the same problem. Finally, we consider algorithmic questions about increasing the orbits of finite words and apply these results to show that, among others, the finiteness problem for (subgroups of) automaton groups of bounded activity is decidable.
Open Access
Computational and logical aspects of infinite monoids
(2003) Lohrey, Markus; Diekert, Volker (Prof. Dr.)
The present work contains a treatise of several computational and logical aspects of infinite monoids. The first chapter is devoted to the word problem for finitely generated monoids. In particular, the relationship between the the computational complexity of the word problem and the syntactical properties of monoid presentations is investigated. The second chapter studies Cayley-graphs of finitely generated monoids under a logical point of view. Cayley-graphs of groups play an important role in combinatorial group theory. We will study first-order and monadic second-order theories of Cayley-graphs for both groups and monoids. The third chapter deals with word equations over monoids. Using the graph product operation, which generalizes both the free and the direct product, we generalize the seminal decidability results of Makanin on free monoids and groups to larger classes of monoids.
Open Access
Formal language theory of logic fragments
(2014) Lauser, Alexander; Diekert, Volker (Prof. Dr.)
The present thesis consists of two parts. Based on syntactic closure axioms of formula sets, the first part gives a formal definition of logic fragments. It also shows the versatileness of this notion of logic fragments, inter alia, giving, C-variety descriptions of logic fragments and abstractly investigating the influence of certain predicates on the expressiveness of logic fragments. The second part considers two-variable first-order logic FO2. A combinatorial description in terms of so-called rankers is given for all full levels as well as all half levels of the quantifier alternation hierarchy of FO2 over the order predicate, both with and without the successor predicate. Also in the second part, effective algebraic criteria describing all full levels as well as all half levels of the quantifier alternation hierarchy of FO2 over several signatures are given, yielding in particular decidability of the definability problem.
Open Access
Gegenseitige Simulation von Datenstrukturen
(2002) Petersen, Holger; Diekert, Volker (Prof. Dr.)
Die vorliegende Arbeit stellt einige Ergebnisse zusammen, welche das Verhältnis verschiedener Berechenbarkeitsmodelle zueinander betreffen. Hierbei wird einerseits der Zusatzaufwand (im Bezug auf die Zeitkomplexität) bei der gegenseitigen Simulation solcher Modelle untersucht. Andererseits werden untere Schranken bewiesen oder auch die Unmöglichkeit einer Simulation. Diese Untersuchungen lassen sich einem Bereich zuordnen, der als konkrete Komplexitätstheorie bezeichnet wird.
Open Access
Gleichungen mit regulären Randbedingungen über freien Gruppen
(2000) Hagenah, Christian; Diekert, Volker (Prof. Dr.)
Wir beweisen, daß das Erfüllbarkeitsproblem für Gleichungen mit regulären Randbedingungen über freien Gruppen PSPACE-vollständig ist. Wir zeigen auch, daß eine minimale Lösung einer solchen Gleichung höchstens eine doppelt exponentielle Länge hat und in 2-DEXPTIME berechnet werden kann. Wir reduzieren zuerst das Problem Gleichungen mit regulären Randbedingungen über einer freien Gruppen zu lösen auf das Problem Gleichungen mit regulären Randbedingungen über freien Monoiden mit einer Anti-Involution zu lösen. Anschließend stellen wir einen Algorithmus vor, der in PSPACE entscheidet, ob diese Gleichungen lösbar sind und einen Algorithmus, der in 2-DEXPTIME eine Lösung berechnet, wenn die Gleichung lösbar ist.
Open Access
Komplexitäts- und Entscheidbarkeitsresultate für inverse Monoide mit idempotenter Präsentation
(2006) Ondrusch, Nicole; Diekert, Volker (Prof. Dr.)
Wir haben eine Konstruktion inverser Monoide $FIM(\Gamma)/P$ und $IM(G)/P$, beruhend auf Arbeiten von Birget und Rhodes sowie Margolis und Meakin betrachtet und konnten für dies speziellen Klassen inverser Monoide mit idempotenter Präsentation die Entscheidbarkeit des Wortproblems in linearer Zeit (auf einer RAM) zeigen. Ferner ist das uniforme Wortproblem für diese inversen Monoide EXPTIME-vollständig. Wir haben ferner die relationale Struktur $\C(\IM(G)/P)$ mit Prädikat $\reach_L$ betrachtet. Hierfür konnten wir die FO-Theorie auf die MSO-Theorie des Cayeyleygraphen von $G$ reduzieren und haben damit die Entscheidbarkeit der FO-Theorie von $\C(\IM(G)/P)$ erhalten. Diese impliziert, wie wir in Kapitel \ref{rationale mengen} gesehen haben, eine Reihe weiterer Resultate, insbesondere die Entscheidbarkeit des verallgemeinerten Wortproblems für $\IM(G)/P$ sowie die Entscheidbarkeit des Leerheitsproblems für boolesche Kombinationen rationaler Mengen in $\IM(G)/P$. Es stellt sich die Frage, für welche Monoide $M$ die Struktur $\C(M)$ noch entscheidbar ist, bzw. für welche Monoide Unentscheidbarkeit gezeigt werden kann.
Open Access
Local divisors in formal languages
(2016) Walter, Tobias; Diekert, Volker (Prof. Dr.)
Regular languages are exactly the class of recognizable subsets of the free monoid. In particular, the syntactic monoid of a regular language is finite. This is the starting point of algebraic language theory. In this thesis, the algebraic connection between regular languages and monoids is studied using a certain monoid construction - local divisors. Using the local divisor construction, we give a Rees decomposition of a monoid into smaller parts - the monoid is a Rees extension of a submonoid and a local divisor. Iterating this concept gives an iterated Rees decomposition of a monoid into groups appearing in the monoid. This decomposition is similar to the synthesis theorem of Rhodes and Allen. In particular, the Rees decomposition shows that closure of a variety V of finite monoids under Rees extensions is the variety H̅ induced by the groups H contained in V. Due to the connection between H̅ and local divisors, we turn our attention to a language description of H̅. The language description is a continuation of classical work of Schützenberger. He studied prefix codes of bounded synchronization delay and used those codes to give a language description of H̅ in the case that the variety H of groups contains only abelian groups. We use the local divisor approach to generalize Schützenberger's language description of H̅ for all varieties H of finite groups. The main ingredient of this generalization is the concept of group-controlled stars. The group-controlled star is an operation on prefix codes of bounded synchronization delay which generalizes the usual Kleene star. The language class SDH(A∞) is the smallest class which contains all finite languages and is closed under union, concatenation product and group-controlled stars for groups in H. We show that SDH(A∞) is the language class corresponding to H̅. As a by-product of the proof we give another language characterization of H̅: the localizable closure LocH(A∞) of H. In the last part of this thesis, we deal with Church-Rosser congruential languages (CRCL). A language is Church-Rosser congruential if it is a finite union of congruence classes modulo a finite, confluent and length-reducing semi-Thue system. This yields a linear time algorithm for the membership problem of a fixed language in CRCL. A natural question, which was open for over 25 years, is whether all regular languages are in CRCL. We give an affirmative answer to this question by proving a stronger statement: for every regular language L and for every weight, there exists a finite, confluent and weight-reducing semi-Thue system S such that A*/S is finite and recognizes L. Lifting the result from the special case of length-reducing to weight-reducing allows the use of local divisors. Next, we focus on Parikh-reducing Church-Rosser systems for regular languages. Instead of constructing a semi-Thue system for a fixed weight, a Parikh-reducing Church-Rosser system is weight-reducing for every weight. We construct such systems for all languages in A̅b̅, that is, for all languages such that the groups in the syntactic monoid are abelian. Additionally, small changes in the proof of this result also yield that for all languages L over a two letter alphabet there exists a Parikh-reducing Church-Rosser system S of finite index such that L is recognized by A*/S. Lastly, we deal with the size of the monoid A*/S for the constructed systems S. We show that in the group case this size has an exponential lower bound and a triple exponential upper bound. The key observation is that one can restrict the alphabet used in the inductive construction. Using the same observation, one can lower the upper bound in the general monoid case from a non-primitive function without this optimization to a quadruple exponential upper bound.
Open Access
Logical fragments for Mazurkiewicz traces : expressive power and algebraic characterizations
(2006) Kufleitner, Manfred; Diekert, Volker (Prof. Dr.)
Mazurkiewicz trace are a model for concurrency. They can be seen as a generalization of words by introducing partial commutation between specific letters. Several logical and language-theoretic characterizations of the variety of monoids DA are known for words. We show which of them also hold for traces and which of them do not hold. An important tool for this task are Ehrenfeucht-Fraisse games. For several logical fragments, we introduce characterizations in terms of these games. They are used to separate logical fragments over traces that have the same expressive power over words. An essential property is, whether one can express concurrency within a fragment or not.
Open Access
The parallel complexity of certain algorithmic problems in group theory
(2017) Kausch, Jonathan; Diekert, Volker (Prof. Dr.)
In this thesis, we study the parallel complexity of certain problems in algorithmic group theory. These problems are the word problem, the geodesic and normal form problem and the conjugacy problem. We study these problems for some products of groups, namely direct products, free products and graph products. For all those we consider the problems for a fixed group as well as the uniform versions. Uniform means that the group is part of the input. Among the studied problems, the word problem is the most important one and necessary to solve any of the other problems. For direct products, solving any of the mentioned problems reduces directly to the problems in the base groups of the product. Some of the solutions for the direct product are required for solving the problems of the more complicated products. For free products, we show that the word problem reduces in AC^0 to the word problem of the base groups and the word problem of the free group of rank two. This does hold for the word problem of a fixed free product as well as for the uniform version. For the geodesic and normal form problem of free products, we introduce an equivalence relation. This relation can be decided in AC^0 by using oracle calls to the word problems of the base groups. The solution of the word and geodesic problem can then be used to solve the conjugacy problem. In free products, two cyclically reduced words are conjugate if and only if they are transposed. Direct products and free products are special cases of graph products. A graph product can be written as an amalgamated product of smaller graph products. We first solve the word problem of some restricted amalgamated product. This solution can then be used to solve the word problem of a fixed graph product inductively. We obtain that the word problem of a fixed graph product is AC^0-reducible to the word problem of its base groups and the word problem of the free group of rank two. Unfortunately, this method cannot be used to solve the uniform word problem. We show that the uniform word problem of graph products is NL-hard. For solving it, we introduce an embedding of the graph product into the automorphism group of some (possibly infinite dimensional) vector space. We show that the evaluation of these automorphisms can be realized in GapL and that verifying its result is in CL by using oracle calls to the word problem in the base groups. The uniform word problem of graph products can be reduced to the evaluation of these automorphisms. For the geodesic problem, we introduce another equivalence relation. As for free products, this relation can be decided in AC^0 by using oracle calls to the (uniform) word problem. In graph products the normal form of some word is the length-lexicographic first equivalent word. For solving the normal form problem, first a geodesic and then the lexicographic normal form of this geodesic is computed. We show that for a fixed graph product the computation of the lexicographic normal form is in TC^0 and TC^0-complete for most graph products. We further show that the uniform version is FNL-complete. The solution of the word and geodesic problem can then be used to solve the conjugacy problem. First, we show how to compute cyclically reduced words in AC^0 by using oracle calls to the word problem. Then we show that in graph products two cyclically reduced words are conjugate if and only if they are obtained by a sequence of transpositions. This problem can then be solved by verifying whether the first word is a factor of some power of the second word. For a fixed graph product the factor problem can be decided in AC^0 by using oracle calls to the word problem. For the uniform factor problem we show that it can be decided in NL by using oracle calls to the uniform word problem. Combining all this gives a solution to the (uniform) conjugacy problem of graph products.
Open Access
Reguläre Häufigkeitsberechnungen
(2005) Austinat, Holger; Diekert, Volker (Prof. Dr.)
Die vorliegende Arbeit beschäftigt sich mit Häufigkeitsberechnungen, einem rekursionstheoretischen Begriff, der in den 60er Jahren von Rose eingeführt wurde. Eine Funktion f ist berechenbar mit Frequenz m/n, wenn es einen Algorithmus gibt, der für je n verschiedene Eingaben n Ausgabewerte berechnet, von denen mindestens m mit den zugehörigen Funktionswerten von f übereinstimmen. Eine erste natürliche Fragestellung war: gibt es nicht-berechenbare Funktionen, die mit einer Frequenz nahe 1 berechnet werden können? Trakhtenbrot beantwortete diese Frage 1963 negativ, indem er zeigte, dass eine Funktion mit Frequenz echt größer als 1/2 bereits berechenbar im herkömmlichen Sinne ist. Andererseits gibt es überabzählbar viele Funktionen, die sich mit Frequenz 1/2 berechnen lassen. Also ist dieses Ergebnis optimal. Die Forschung auf diesem Gebiet intensivierte sich daraufhin: Wissenschaftler wie Dëgtev, Kinber und Trakhtenbrot selbst (in den 70er und 80er Jahren) und Beigel, Gasarch, Hinrichs, Kummer, Stephan, Tantau und Wechsung (ab den 90er Jahren) beschäftigten sich mit verschiedenen Aspekten von Häufigkeitsberechnungen und verwandten Berechenbarkeitsbegriffen. In der vorliegenden Arbeit beschäftigen wir uns vorwiegend mit regulären Häufigkeitsberechnungen, also solchen, die von endlichen Automaten vorgenommen werden können. Kinber untersuchte diesen Aspekt als erster im Jahre 1976 und behauptete, dass sich Trakhtenbrots Resultat auf endliche Automaten überträgt. Sein folgerte dies aus einem allgemeineren Resultats über separierbare Sprachen, das sich allerdings als falsch herausstellte (ein Gegenbeispiel wurde 2002 von Tantau angegeben). (Zwei disjunkte Sprachen A und B heißen separierbar, wenn ein Algorithmus alle Wörter aus A akzeptiert und alle Wörter aus B ablehnt). Die Frage, ob das Analogon von Trakhtenbrots Resultat für endliche Automaten gilt, stellte sich also von neuem. Diese Dissertation enthält folgende Ergebnisse. In Kapitel 2 geben wir zwei Beweise für Trakhtenbrots Resultat an. Zunächst präsentieren wir seinen Originalbeweis, um dann einen neuen kombinatorischen Beweis zu geben, der einen großen Vorteil besitzt: er erlaubt die Übertragung des Ergebnisses auf endliche Automaten. Zwei kleinere Resultate beschließen dieses Kapitel: der Nachweis, dass es überabzählbar viele nicht häufigkeitsberechenbare Sprachen gibt, und eine Darstellung des Zusammenhangs von Häufigkeitsberechnungen und sog. mulit-selektiven Mengen. In Kapitel 3 arbeiten wir den Fehler in Kinbers Beweis über separierbare Sprachen heraus und geben ein konkretes Gegenbeispiel an. Dann untersuchen wir die Separierbarkeit von sog. Pfad- und Anti-Pfadsprachen, die wie folgt definiert sind: sei alpha ein unendliches Wort über dem Alphabet { 0, 1 }; dann ist A(alpha) die Menge der endlichen Präfixe von alpha, und B(alpha) die Menge der Wörter von A(alpha), bei denen das letzte Bit negiert wurde. Wir zeigen, dass A(alpha) und B(alpha) genau dann separiert werden können, wenn die 1-Positionen von alpha berechnet werden können. Andererseits gibt es überabzählbar viele alpha, für die A(alpha) und B(alpha) mit Frequenz 1/2 berechnet werden können. Wenn (ab drei Eingaben) nur ein Fehler zugelassen ist, dann sind A(alpha) und B(alpha) bereits rekursiv. Dieses Ergebnis überträgt sich auch auf endliche Automaten. Zum Abschluss dieses Kapitels zeigen wir, dass sich Kinbers Vermutung (dass Trakhtenbrots Resultat auch für Sprachen gilt, die durch endliche Automaten separiert werden können) nicht retten lässt: für jede Konstante q < 1 gibt es Werte 1 <= m < n mit m/n > q und ein alpha derart, dass A(alpha) und B(alpha) durch endliche Automaten mit Frequenz m/n separiert werden können, jedoch nicht rekursiv separierbar sind. In Kapitel 4 untersuchen wir verschiedene Aspekte regulärer Häufigkeitsberechnungen. Wir zeigen zunächst, dass sich Trakhtenbrots Resultat auf endliche Automaten überträgt, indem wir den neuen Beweis aus Kapitel 2 nochmals genauer betrachten. Anschließend zeigen wir, dass aperiodische Automaten, die Häufigkeitsberechnungen durchführen, nur aperiodische reguläre Sprachen berechnen können (aperiodische Sprachen entsprechen sternfreien Sprachen). Dann beweisen wir ein sog. Iterationskriterium, das vergleichbar mit dem bekannten Pumping-Lemma für reguläre Sprachen ist und uns für viele konkrete Beispielsprachen den Nachweis erlaubt, dass diese nicht häufigkeitsberechenbar sind. Im letzten Teil untersuchen wir dann Abschlusseigenschaften der Klasse der regulär häufigkeitsberechenbaren Sprachen: wir zeigen, dass sie eine boolesche Algebra bilden, jedoch nicht unter Spiegelung abgeschlossen sind. Darüberhinaus ist die Vereinigung zweier Sprachen, die mit Frequenz 1/n erkennbar sind, in der Regel nicht 1/n-erkennbar. Wir beweisen eine untere Schranke, die sehr nah an der besten bekannten oberen Schranke liegt.
Open Access
Similarity search with set intersection as a distance measure
(2010) Hoffmann, Benjamin Sascha; Diekert, Volker (Prof. Dr.)
This thesis deals with a fundamental algorithmic problem. Given a database of sets and a query set, we want to determine a set from the database that has a maximal intersection with the query set. It is allowed to preprocess the database so that queries can be answered efficiently. We solve the approximate version of this problem. We investigate two randomized input models which are derived from real inputs. We present a deterministic algorithm for each of them. Under the assumption that the database and the query set follow one of these models, the corresponding algorithm determines with high probability a set from the database that has no maximal intersection with the query set, but an intersection that achieves a large proportion of the maximal size. Depending on the model, the query time is either quasi-linear in the sum of the database size and the number of different elements from all sets, or it is polylogarithmic in the database size. Thus, both algorithms are significantly faster than a naive algorithm intersecting the query set with each single database set.