guest ::
%0 Thesis %A Repke, Stefan %T Simplification problems for automata and games %C Aachen %I Publikationsserver der RWTH Aachen University %M RWTH-CONV-145203 %P VII, 93 S. : graph. Darst. %D 2014 %Z Zsfassung in dt. und engl. Sprache %Z Aachen, Techn. Hochsch., Diss., 2014 %X 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. %K Automatentheorie (SWD) %K Unendliches Spiel (SWD) %K Kellerautomat (SWD) %F PUB:(DE-HGF)11 %9 Dissertation / PhD Thesis %U https://publications.rwth-aachen.de/record/444885