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

Jančar, Petr; Mráz, František; Plátek, Martin; Vogel, Jörg

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.

MSC:

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

Keywords:

automata with a restart operation