Restarting automata. The standard type of restarting automaton and its variants (Q6938646)

The contribution is the first volume of a planned two-volume treatment of the theoretical properties of restarting automata. A restarting automaton is essentially a two-way finite-state automaton that processes an input with the help of a finite-state control. However, a restarting automaton has two additional features. First, at any point during the computation it can replace a segment of the tape (like the sequence ``aaa'') by a (usually) shorter segment (like ``ab''). Second, at any point during the computation it can restart its computation from the beginning of the current tape contents (after any number of replacements were carried out). This operational device was introduced to model a linguistic approach to parsing of free word-order languages called ``analysis by reduction''. In this approach, which never became widely popular in computational linguistics, a sentence of a natural language is analyzed by successively simplifying the sentence (e.g., removing adjectives of noun phrases). These simplifications are modeled by the length-reducing replacements of restarting automata and the iterated simplifications are achieved by means of restarts. Eventually, no further simplifications are possible and the remaining sentence is analyzed directly. This is achieved in a restarting automaton by accepting an input directly without any replacements or restarts.\N\NThe book is subdivided into four chapters. Chapter 1 is a very gentle introduction to the notation and the general notion of phrase-structure grammars including various restrictions. Additionally, the concept of ``analysis by reduction'' and the general model of a restarting automaton are introduced. These introductions are flanked by examples, intuitions and explanations as well as motivation. The author assumes essentially no prior knowledge on any of these concepts including the grammars in the Chomsky hierarchy. While plenty of intuition is provided, the definitions are presented in full formal details. The two main properties, called ``correctness preservation'' and ``error preservation'', are introduced as well and essentially express that the simplifications (i.e., replacements) performed preserve the validity or invalidity of the sentence. These properties are automatically true for restarting automata since they decide validity (i.e., accept or reject) on the final form after simplifications and transfer that result to the original input. In other words, the original input is accepted if and only if there is a sequence of replacements and restarts that is licensed by the restarting automaton such that the restarting automaton eventually accepts.\N\NThe main chapter is Chapter 2, in which many, many variations of restarting automata are investigated and compared in terms of their expressive power. Besides comparisons among various restarting automata, also comparisons to standard classes of formal language theory are presented. The number of variations that are considered is impressively extensive and covers any imaginable restriction. This part thus collects a vast body of literature in a reader-friendly, unified, and systematic manner. While all of these results are available in the literature, they have progressively been developed, usually by the author and his co-authors, across several decades. Once again, ample intuition and explanations are provided and the author presents full details as well as proof outlines for all claims. This chapter certainly develops the most comprehensive overview of the impact of various restrictions on the expressive power. The relations to the language classes of the (extended) Chomsky hierarchy provide anchors for the readers. With the help of these results the linguistically informed reader should easily be able to select a variation of restarting automata that is suitable for the analysis of the (natural) language under consideration.\N\NChapter 3 investigates the descriptional complexity of various variants of restarting automata. The descriptional complexity expresses how expensive it is to describe a certain language by means of a certain model. While two variations of restarting automata maybe shown to be equally expressive, it may still be significantly simpler (i.e., less complex) to express a given language by means of one of the variations. These worst-case trade-offs are the subject matter in this chapter. In other words, given a language that can be expressed by variation~1 with complexity~\(n\) (usually the number of states), how complex is it to express this language by variation~2. For example, it is well known that nondeterministic finite automata can be exponentially more succinct than their deterministic counterparts, which means that there is a family \((L_1, L_2, \dotsc)\) of languages such that the smallest nondeterministic finite-state automaton for \(L_n\) only requires \(n\) states, while the smallest deterministic finite-state automaton for \(L_n\) requires \(2^n\) states. These investigations give valuable insight into the best choice among multiple expressively equivalent variations of restarting automata.\N\NThe final chapter is devoted to the learnability for variations of restarting automata. As expected, there are multiple learning scenarios that depend on the type of available training data (positive or negative examples), the condition for success, and the availability of other resources. To learn proper replacements, a restarting automaton ideally also has access to examples of proper simplifications, so most results in this chapter resemble results for learning finite-state transducers. An appendix collects the open questions that are covered in this book.\N\NOverall the book is an excellent resource for people who are interested in the capabilities of restarting automata and the ease of specification for various subclasses. The book promises the most comprehensive review of the expressive power of (subclasses of) restarting automata and, given the author's eminent role in their development, there is little doubt that the book provides exactly that. The writing is clear and all details are provided. Full proof details can always be found in the referenced original literature, but the presented proof ideas are often sufficient. Since all notions and notations are covered and no prior knowledge or experience is assumed, the contribution is suitable for any graduate with an interest in the topic.