Restarting Automata

Focusing on restarting automata, this monograph explores their definition and evolution, initially motivated by linguistic analysis techniques applicable to languages with flexible word order. It details the operational mechanics of these automata, including their finite-state control and tape manipulation. The work compiles various results on different types of restarting automata, examining their expressive capacity, descriptional complexity, and applications in distributed systems. This comprehensive guide serves as a reference for researchers and a textbook for advanced studies in formal language and automata theory.