Simplification problems for automata and games

Repke, Stefan; Thomas, Wolfgang; Löding, Christof; Colcombet, Thomas

doi:33625

Simplification problems for automata and games = Vereinfachungsprobleme für Automaten und Spiele

Repke, Stefan (Author)

2014

Verantwortlichkeitsangabevorgelegt von Stefan Repke (geb. Schulz)

ImpressumAachen : Publikationsserver der RWTH Aachen University 2014

UmfangVII, 93 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2014

Zsfassung in dt. und engl. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Löding, Christof (Thesis advisor)^RWTH* ; Thomas, Wolfgang (Thesis advisor) ; Colcombet, Thomas (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2014-05-13

Online
URN: urn:nbn:de:hbz:82-opus-51188
URL: http://publications.rwth-aachen.de/record/444885/files/5118.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Automatentheorie (Genormte SW) ; Unendliches Spiel (Genormte SW) ; Kellerautomat (Genormte SW) ; Informatik (frei) ; automata theory (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Die Vereinfachung von Automaten beschäftigt sich mit der Frage, ob ein gegebener Automat in ein simpleres Format überführt werden kann; d.h., ob im gegebenen Fall ein bestimmtes Merkmal des Automatenmodells verzichtbar ist. Wenn ja, so soll ein vereinfachter Automat generiert werden. Die zugrundeliegende Motivation ist, dass einfachere Automaten bessere theoretische Eigenschaften besitzen. Vereinfachung können auch für Spiele betrachtet werden, die durch Automaten definiert sind. Dabei lautet die Frage, ob Gewinnstrategien durch Automaten dargestellt werden können, deren Format simpler ist als die Spielspezifikation. Diese Arbeit widmet sich zwei Aspekten der Vereinfachung: Regularitätsproblemen und vorausschauender Delegierung. Beim Regularitätsproblem geht es darum, zu entscheiden, ob ein gegebener deterministischer Kellerautomat (DPDA) eine reguläre Sprache erkennt. Diese Frage wurde vor Jahrzehnten gelöst, wohingegen das erweiterte Problem für w-DPDAs (welche unendliche Eingaben verarbeiten) seitdem offen geblieben ist. Wir erweitern eine Methode, die es erlaubt, bekannte Ergebnisse über DPDAs zu verallgemeinern auf w-DPDAs mit schwacher Akzeptanz. Für diese schwachen w-DPDAs zeigen wir die Entscheidbarkeit des Regularitätsproblems und zusätzlich des Äquivalenzproblems. Für w-DPDAs im Allgemeinen geben wir eine Kongruenzrelation an, die Regularität charakterisiert. Die Entscheidbarkeit bleibt hingegen offen. Eine verallgemeinerte Variante des Regularitätsproblems beschäftigt sich mit Pushdown-Spielen (PDGs), d.h., Zwei-Spieler-Spiele welche durch w-DPDAs beschrieben werden und für welche Gewinnstrategien ebenfalls durch DPDAs dargestellt werden können.Regularität bedeutet entsprechend, dass ein PDG eine reguläre Gewinnstrategie besitzt; d.h., sie ist darstellbar durch einen endlichen Automaten. Wir zeigen dass diese Form des Regularitätsproblems bereits unentscheidbar ist für PDGs mit Sicherheitsbedingung. Ein anderer Aspekt der Vereinfachung beschäftigt sich mit vorausschauender Delegierung für nichtdeterministische endliche Automaten (FSAs).Das Problem ist hier, zu entscheiden, ob Transitionen deterministisch gewählt werden können, wenn man eine beschränkte Vorschau auf die Eingabe zugesteht.Eine solche Auswahlfunktion nennt man Delegierer.Nicht-triviale Komplexitätsergebnisse über die Existenz von Delegierern sind bisher nur bekannt für eine eingeschränkte Unterklasse von FSAs. Wir erbringen entsprechende Ergebnisse für (uneingeschränkte) FSAs und zeigen, dass es PSPACE-vollständig ist, zu entscheiden, ob ein Delegierer für eine beliebige Vorschaubeschränkung existiert und einen solchen zu bestimmen. Weiterhin zeigen wir mithilfe von Zwei-Spieler-Spielen, dass die Existenz eines Delegierers in Polynomialzeit entschieden werden kann, wenn die Vorschaubeschränkung konstant ist.

Automata simplification asks whether a given automaton can be converted into one of a simpler format, i.e., whether a certain feature of the automaton model is avoidable in the given case.If yes, an automaton of this simpler format shall be synthesized. The idea is that simpler automata models have better closure and algorithmic properties. Simplification can also be studied for games that are defined by automata. Then, the question is whether winning strategies can be implemented by automata of a format that is simpler than the one used for the game specification. In this thesis, we continue the research on two different aspects of simplifications, namely regularity problems and lookahead delegation. The regularity problem is to decide whether a given deterministic pushdown automaton (DPDA) recognizes a regular language; which means that the pushdown stack is unnecessary as an equivalent finite state automaton can be found. This problem was solved decades ago for DPDAs whereas its pendant for w-DPDAs (working on infinite input sequences) remained open since then. For those weak w-DPDAs, we show the regularity problem and further the equivalence problem to be decidable. For the general case of w-DPDAs, we define a congruence relation that characterizes regularity, whereas besides this theoretical connection,the decidability remains open, unfortunately. A generalized variant of the regularity problem concerns pushdown games (PDGs), i.e., two-player games which are specified by w-DPDAs and which omit a winning strategy representable by a DPDA, too. In this setting, regularity means that there is a regular' winning strategy, i.e., one representable by a finite state automaton. We show the regularity problem to be undecidable even for PDGs with safety acceptance. The other aspect of simplification deals with lookahead delegation for nondeterministic finite state automata (FSAs). The problem is to decide whether transitions can be chosen deterministically when a bounded lookahead on the input word is allowed. Such a choice function is called delegator.Nontrivial complexity results on the existence of delegators are only known for a restricted subclass of FSAs, yet. We contribute the corresponding results for (unrestricted) FSAs. We provide polynomial space upper and lower bounds for deciding the existence of a delegator with some bounded lookahead (and synthesizing it). By using two-player games as a tool, we further prove that the existence can be decided in polynomial time if the length of the lookahead is fixed.

Fulltext:
PDF