On Monotonic Automata with a Restart Operation
Petr Jančar, František Mráz, Martin Plátek, Jörg Vogel · 1999
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 monotonocity 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.