|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040401,
author = {Jan\v{c}ar, Petr and Mr\'{a}z, Franti\v{s}ek
and Pl\'{a}tek, Martin and Vogel, J\"{o}rg},
title = {On Monotonic Automata with a Restart Operation},
journal = jalc,
year = 1999,
volume = 4,
number = 4,
pages = {287--311},
keywords = {monotonic automata, monotonic automata with a restart
operation, context-free languages},
abstract = {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.}
}