25 Years of Restarting Automata:
           Lots of Results and Open Problems

                                 Friedrich Otto?

The restarting automaton was introduced by Petr Jančar, František Mráz, Mar-
tin 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 morpho-
logical, syntactical, and/or semantical information on the various word forms
(morphemes) of the sentence, this sentence is repeatedly simplified by local trans-
formations 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. Ac-
cordingly, 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. With-
out 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–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

  Copyright c 2020 for this paper by its authors. Use permitted under Creative Com-
  mons License Attribution 4.0 International (CC BY 4.0).
?
  Friedrich Otto is a retired professor of Computer Science from the University of
  Kassel in Germany. He has done research in rewriting systems, semigroup theory,
  automata theory, and formal languages.
2       Friedrich Otto

symbols of a restarting automaton should have some linguistically meaningful
interpretation, are discussed.


References
 1. Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: Reichel,
    H. (ed.), FCT’95, Proc., Lecture Notes in Computer Science 965, pp. 283–292,
    Springer, Heidelberg (1995)
 2. Plátek, M., Lopatková, M., Oliva, K.: Restarting automata: motivations and ap-
    plications. In: Holzer, M. (ed.), Workshop “Petrinets” und 13. Theorietag “Auto-
    maten und Formale Sprachen, Proc., pp. 90–96, Institut für Informatik, Technische
    Universität München (2003)
 3. Jurdziński, T., Otto, F.: Shrinking restarting automata. International Journal of
    Foundations of Computer Science 18 (2007) 361–385.
 4. Jančar, P., Mráz, F., Plátek, M., Vogel, J.: On monotonic automata with a restart
    operation. Journal of Automata, Languages and Combinatorics 4 (1999) 287–311.
 5. Jurdziński, T., Loryś, K., Niemann, G., Otto, F.: Some results on RWW- and
    RRWW-automata and their relation to the class of growing context-sensitive lan-
    guages, Journal of Automata, Languages and Combinatorics 9 (2004) 407–437.
 6. Niemann, G., Otto, F.: Restarting automata, Church-Rosser languages, and rep-
    resentations of r.e. languages. In: Rozenberg, G., Thomas, W. (eds.), DLT 1999,
    Proc., World Scientific, Singapore, 2000, 103–114.
 7. Plátek, M., Otto, F.: On h-lexicalized restarting automata. In: Csuhaj-Varjú, E.,
    et al. (eds.), AFL 2017, Proc., EPTCS 252 (2017) 219–233.
 8. Mráz, F., Otto, F., Pardubská, D., Plátek, M.: Lexicalized syntactic analysis by
    restarting automata. In: Holub, J., Žd’árek, J. (eds.), PSC 2019, Proc., Czech
    Technical University, Prague, 2019, 69–83.