Jančar, Petr; Mráz, František; Plátek, Martin; Vogel, Jörg On monotonic automata with a restart operation. (English) Zbl 0942.68064 J. Autom. Lang. Comb. 4, No. 4, 287-311 (1999). Summary: Automata with a restart operation define a special class of rewrite (reduction) systems which has a close relation to the dependency syntax of natural languages. We impose a natural condition of monotonicity and introduce a hierarchical structure of several versions of such automata. The language classes recognized by these automata form a proper hierarchy, with the class of context-free languages on the top, and with the class of deterministic context-free languages on the bottom. In particular, the deterministic monotonic versions of all the introduced automata recognize the same class of languages namely that of deterministic context-free languages. Cited in 25 Documents MSC: 68Q45 Formal languages and automata 68Q42 Grammars and rewriting systems Keywords:automata with a restart operation PDF BibTeX XML Cite \textit{P. Jančar} et al., J. Autom. Lang. Comb. 4, No. 4, 287--311 (1999; Zbl 0942.68064) OpenURL