In the literature various types of restarting automata have been studied that are basedon contextual rewriting. A word w is accepted by such an automaton if,starting from the initial configuration that corresponds to input w, theword w is reduced to the empty word by a finite number of applications ofthese contextual rewritings. This approach is reminiscent of the notion of McNaughtonfamilies of languages. Here we put the aforementioned types of restarting automata intothe context of McNaughton families of languages, relating the classes of languagesaccepted by these automata in particular to the class GCSL of growing context-sensitivelanguages and to the class CRL of Church–Rosser languages.
