Browsing by Author "Wächter, Jan Philipp"

Now showing 1 - 3 of 3

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
Kaskadenzerlegung spezieller Automatenklassen
(2013) Wächter, Jan Philipp
Der Begriff des endlichen Automaten spielt für die Informatik eine große Rolle. Vom Chip-Design über die Progammimplementierung bis hin zur Sprach- und Automatentheorie findet er Anwendung. Dies ist Grund genug sich mit endlichen Automaten genauer zu beschäftigen. Auf algebraischer Seite ist der endliche Automat eng verwandt mit der Halbgruppe oder dem Monoid. Zwar sind diese Konzepte weniger anschaulich als ein endlicher Automat, sie erlauben jedoch einen anderen Blickwinkel und machen die mathematische Betrachtung an einigen Stellen einfacher. Durch das Krohn-Rhodes-Theorem ist bekannt, dass sich eine beliebige endliche Halbgruppe in einfache Gruppen und FlipFlops zerlegen lasst. Die Rückkopplungsfreiheit dieser Zerlegung motiviert den Begriff der "Kaskadenzerlegung". Während die einfachen Gruppen, die dabei auftreten, in der ursprünglichen Halbgruppe selbst enthalten sind, ist dies beim FlipFlop nicht notwendigerweise der Fall. Es stellt sich daher die Frage: Gibt es eine Menge von strukturell möglichst einfachen Halbgruppen, die als Bausteine eine Zerlegung jeder – auch komplexeren – Halbgruppe so ermöglichen, dass jeder verwendete Baustein in der Halbgruppe selbst enthalten ist? Ist die Menge endlich und wie funktioniert die Zerlegung? Angetrieben durch diese Fragestellung werden in dieser Arbeit Zerlegungen von Halbgruppen und Monoiden aus speziellen Klassen genauer untersucht, für die die Frage nach den Bausteinen beantwortet werden kann.
Open Access
Das Wortproblem für Omega-Terme über Zweivariablenlogik
(2014) Wächter, Jan Philipp
Kaum ein Maschinenmodell ist von so großer Bedeutung wie das der endlichen Automaten. Es findet nicht nur Anwendung in der technischen, theoretischen und praktischen Informatik, sondern auch in vielen anderen Wissenschaften und Wissenschaftsbereichen. Von daher mag es kaum verwundern, dass nicht nur die mit den endlichen Automaten untrennbar verbundenen regulären Sprachen, sondern auch viele darin enthaltene Sprachklassen von großem akademischen und praktischen Interesse sind. Neben der automatentheoretischen Untersuchung der regulären Sprachen gibt es daher noch andere Herangehensweisen: beispielsweise durch Logiken oder durch algebraische Strukturen. Dass es sich bei endlichen Automaten um recht einfache Maschinen handelt, überträgt sich auch auf die algebraischen Strukturen. So werden reguläre Sprachen durch endliche Monoide erkannt, einer algebraischen Struktur, die nur wenigen Axiomen gerecht werden muss. Ein Sprachklasse unterhalb der regulären Sprachen erhält man beispielsweise, indem man sich auf Sprachen beschränkt, die durch Sätze der Prädikatenlogik erster Stufe oder "first-order logic" FO definierbar sind. Durch Beschränkung der Anzahl der in einem solchen Satz erlaubten Variablen lässt sich diese Sprachklasse weiter spezialisieren. Es ist bekannt, dass die Verwendung von nur drei Variablen keine Einschränkung darstellt. Die Untersuchung jener Sprachen, die sich mit Prädikatenlogik erster Stufe unter Verwendung von nur zwei Variablen, also durch die Zweivariablenlogik FO2[<] definieren lassen, ergibt sich daher auf natürliche Weise. Auf algebraischer Seite korrespondiert diese Klasse von Sprachen mit der Menge endlicher Monoide, genauer der Varietät endlicher Monoide DA. Jene Varietät DA erhält man auch durch Vereinigung der abzählbar unendlich hohen, sogenannten Trotter-Weil-Hierarchie. Diese besteht aus Ecken, Join-Ebenen und Schnitt-Ebenen und ist zentraler Gegenstand der Betrachtungen dieser Arbeit. Diese Betrachtungen befassen sich mit dem Wortproblem für Omega-Terme von Varietäten in der Trotter-Weil-Hierarchie. Bei Omega-Termen oder, wie sie hier genannt werden, Pi-Termen handelt es sich um Terme von Variablen, die mit einer zusätzlichen Pi-Potenz versehen werden können. Anschließend können für die Variablen Elemente eines Monoids eingesetzt werden, die Pi-Potenzen erhalten dann einen Wert, der als "unendlich oft" interpretiert werden kann. Anschaulich lässt sich ein Pi-Term daher mit dem Verhalten eines endlichen Automaten, dessen Ausführung nicht durch eine bestimmte Anzahl an Schritten beschränkt ist, verknüpfen. Zwei Pi-Terme u und v lassen sich zu einer Gleichung u = v verknüpfen. Es ist dann möglich zu fragen, ob ein Monoid M diese Gleichung erfüllt. Dies ist dann der Fall, wenn sich links und rechts stets das selbe Monoidelement ergibt, sobald man für die Variablen beliebige Elemente einsetzt. Diese Fragestellung lässt sich erweitern: Erfüllt jedes Monoid in einer Varietät die Gleichung? Dabei handelt es sich um die Frage des Wortproblems für Pi-Terme der Varietät. Diese Arbeit wird zeigt, dass sich das Wortproblem für Pi-Terme der Ecken und Join-Ebenen der Trotter-Weil-Hierarchie durch eine logarithmisch platzbeschränkte nichtdeterministische Turingmaschine entscheiden lässt, dass es also zur Komplexitätsklasse NL gehört. Obwohl es sich bei NL um eine nichtdeterministische Platzklasse handelt, ist dieses Ergebnis interessant, da sich die Probleme aus NL effizient parallel entscheiden lassen. Eine Eigenschaft, die nicht zuletzt seit dem Aufkommen von Mehrkernprozessoren, eine immer größere Rolle spielt. Gleichzeitig liefert ein NL-Algorithmus auch einen deterministischen Polynomialzeitalgorithmus. Der NL-Algorithmus für die Entscheidung des Wortproblems für Pi-Terme der Ecken und Join-Ebenen der Trotter-Weil-Hierarchie lässt sich leicht abwandeln, um die Zugehörigkeit des Wortproblems für Pi-Terme von DA zu NL zu zeigen. Im Sinne der Komplexitätsklassen verbessert dies ein Ergebnis von A.~Moura, das einen deterministischen Polynomialzeitalgorithmus zur Entscheidung dieses Problems liefert und damit Erkenntnisse von Almeida und Zeitoun erweitert, die zeigten, dass sich das Wortproblem für Pi-Terme der Varietät der endlichen R-trivialen Halbgruppen in Linearzeit entscheiden lässt. Die Varietät der endlichen R-trivialen Monoide tritt auch als Ecke in der Trotter-Weil-Hierarchie auf. Das Vorgehen in dieser Arbeit unterscheidet sich von dem Vorgehen in den genannten anderen Arbeiten. Das zentrale Konzept ist dabei das Einsetzen linearer Ordnungstypen für die Pi-Potenzen der Pi-Terme, ähnlich wie bei Huschenbett und Kufleitner. Auf die dabei entstehenden, im Allgemeinen unendlichen, verallgemeinerten Wörter werden dann einige Instrumente, die bei der Untersuchung der Trotter-Weil-Hierarchie sonst in einer endlichen Form vorkommen, übertragen. Am wichtigsten dabei sind die sogenannten Ranker, die auf die "trurtle programs" von Schwentick, Thérien und Vollmer zurückgehen und anschließend u.a. durch Weis und Immerman weiter entwickelt wurden. Über die eindeutige Intervall-Temporallogik von Lodaya, Pandya und Shah ergibt sich ihr Bezug zur Logik.