The restarting automaton was introduced by Petr Jančar, František Mráz, Martin Plátek, and Jörg Vogel in a talk presented at the FCT'95 in Dresden [1]. It is not just another variant of the Turing machine, but it is a machine model that is motivated by the linguistic technique of analysis by reduction [2]. Given a sentence of a natural language, possibly annotated by tags giving morphological, syntactical, and/or semantical information on the various word forms (morphemes) of the sentence, this sentence is repeatedly simplified by local transformations until either an error is detected and the input sentence is rejected, or a correct simple sentence is obtained and the input sentence is accepted. Accordingly, a restarting automaton consists of a flexible tape (or a linked list) that initially contains the input, a finite-state control, and a read/write window of a fixed positive size. It scans the current sentence stored on its tape, performs one or more local transformations, in this way simplifying the stored sentence, and then it restarts, which means that it places its read/write window on the beginning of its tape and resets its finite-state control to the initial state. This sequence of operations, called a cycle, is iterated until the automaton either accepts or rejects.

Actually, the restarting automaton is not simply an automaton, but a whole family of different types of automata. These types differ with respect to the allowed move and rewrite operations, the size of the read/write window, the number of allowed rewrite operations between restarts, the number of non-input symbols in the tape alphabet of the automaton, and the number of states. Without any restrictions on the allowed rewrite operations, the restarting automaton is equivalent to the Turing machine. In order to restrict the expressive capacity of the restarting automaton, it is therefore generally required that each rewrite operation allowed is weight-reducing (see, e.g., [3]) or even length-reducing as in [1].

Using different restrictions the classes of the Chomsky hierarchy have been characterized by various types of restarting automata (see [1,[4][5][6]). In the present talk, these characterizations are presented by considering some of the parameters that are used to specify different types of restarting automata. In addition, the recently introduced notions of h-lexicalized restarting automata and h-lexicalized syntactic analysis [7,8], which are motivated by the idea that all non-input