We introduce a hierarchy of monotonic rewriting automata with a restart operation and show that its deterministic version collapses in a sequence of characterizations of deterministic context-free languages. The nondeterministic version of it gives a proper hierarchy of classes of languages with the class of context-free languages on the top.
展开▼