On monotonic automata with a restart operation. (English) Zbl 0942.68064

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.


68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems