Automata and game theoretic models of computation

Abstract

In this thesis we investigate two finite state models of computation: automata and games on graphs. First we investigate the state complexity of finite word and tree automata from two directions. One direction is to study the interplay between non-deterministic automata (NFA) and deterministic automata (DFA) state complexity. In particular, we show that the exponential gap of the state explosion caused by the subset construction and the complementation of NFA may be filled. Another direction is to investigate the DFA state complexity of natural subclasses of regular languages. We focus on finite word and tree languages and provide improved upper bounds on the state complexity of union and intersection of such languages. Secondly we generalize finite automata by introducing automata over arbitrary algebraic structures. For a structure S, we use the term S-automata for the class of automata operating over S. An S-automaton has a fixed number of registers and processes finite sequences of elements from the (possibly infinite) domain of S. At every stage, it may test the input against the values in the registers using the relations of S and then based on the outcome of this test, move to another state after applying some operations from S to the registers. We investigate certain natural problems such as the validation problem and the emptiness problem and show that they may become decidable or undecidable if we change the underlying structure or the structure of the automaton in various natural ways. Lastly we investigate the problem of solving Büchi and parity games on trees with back-edges. We present an efficient algorithm that solves a Büchi game played on trees with back-edges and then apply our analysis to parity games. We then present experimental evidence which shows that our algorithm for Büchi games performs asymptotically better than the classical algorithm in many cases. Also we present a concrete class of Büchi games for which the classical algorithm has a quadratic running time and our algorithm has linear running time.