Ordered Restarting Automata

The following thesis deals with ordered restarting automata. Restarting automata are a theoretical model used in linguistics for the analysis by reduction. The ordered restarting automata were introduced in the context of two-dimensional picture languages and form the underlying one-dimensional model. Here we look at different variants of this one-dimensional model and examine issues related to language classes and descriptional complexity. A common feature of all these variants is the fixed window size of 3, and that the middle character is replaced by a smaller character in a rewrite step. First of all, we examine the models in which the rewriting process is always connected to a restart. Starting from the deterministic model with states we will soon consider the stateless variant, as it also characterizes the regular languages. This gives us a characterization of the regular languages, which is as simple as that by a DFA. Instead of the states we use tape symbols to measure the size of such an automaton. In addition, we are able to present many languages and language operations more concisely. Moreover, starting from a stateless ordered restarting automaton, which may be deterministic or non-deterministic, we specify a general construction of an NFA with exponentially many states that describes the same language and we show that the construction is optimal except for the constant in the exponent. We then use this construction to show that many interesting decision problems for our stateless restarting automata are PSPACE-complete. Finally, we use the idea of this construction to introduce reversibility for our model.