Restarting Automata

In this unique volume, the expressive capacity of the various types of restarting automata is studied, and the resulting classes of languages are compared to each other and to the classes of an extended Chomsky hierarchy. A restarting automaton consists of a finite-state control, a flexible tape with end-of-tape markers that initially contains the input, and a read-write window of a fixed finite size. The objective here is to collect the many results that have been obtained on the various types of restarting automata in one place and to present them in a uniform and systematic way. Among the book’s topics and features: * Delivers a comprehensive survey of the numerous types of restarting automata and results that obtained on them * Shows how the restarting automaton is motivated by the linguistic technique of ‘analysis by reduction’ * Presents the many types of restarting automata in a uniform and systematic way * Provides a significantly complete list of references on restarting automata * Offers a text that is accessible to advanced undergraduate and graduate students Accordingly, this comprehensive monograph may serve as a book of reference for researchers, as a guide to the literature on restarting automata, and as a textbook for an advanced undergraduate or graduate course in formal language and automata theory.