Restarting automata with auxiliary symbols restricted by lookahead size

摘要

This paper presents a study on lookahead hierarchies for restarting automata with auxiliary symbols. We show that the class of languages for deterministic monotone or monotone restarting automaton, whose restart step and rewrite step are separated, coincides with that of the same type of restarting automaton whose restart and rewrite steps are not separated, for any fixed lookahead size. For the non-monotone deterministic case, the lookahead length must be approximately doubled. We then turn our attention to restarting automata with small lookahead. For the general restarting automaton model, we show that there are just two different classes of languages recognized, through the restriction of lookahead size: those with lookahead size 1 and those with lookahead size 2. We also show that the respective (left-) monotone restarting automaton models characterize the context-free languages and that the respective right-left-monotone restarting automata characterize the linear languages both with just lookahead length 2.