Ordered Restarting Automata

More about the book

This thesis explores ordered restarting automata, a theoretical model in linguistics used for analysis by reduction. These automata were developed in the context of two-dimensional picture languages and serve as a foundational one-dimensional model. The study investigates various one-dimensional variants, focusing on language classes and descriptional complexity, all characterized by a fixed window size of 3, where the middle character is replaced by a smaller character during rewriting. Initially, the research examines models where the rewriting process is always linked to a restart, beginning with the deterministic model with states. The analysis then shifts to the stateless variant, which also characterizes regular languages, providing a straightforward characterization akin to that of a DFA. Here, tape symbols are employed to assess the automaton's size, allowing for a more concise presentation of numerous languages and language operations. From a stateless ordered restarting automaton, whether deterministic or non-deterministic, the thesis outlines a general construction of an NFA with exponentially many states that recognizes the same language, demonstrating that this construction is optimal apart from a constant in the exponent. Additionally, it establishes that many significant decision problems for these stateless restarting automata are PSPACE-complete. The thesis concludes by introducing the concept of reversibi