Restarting automata with auxiliary symbols restricted by lookahead size

Abstract

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.

Keywords:

• restarting automata
• lookahead size
• context-free languages
• Church–Rosser
• linear languages
• lookahead hierarchy
• auxiliary symbols

2010 AMS Subject Classifications::

• 68Q05
• 68Q42
• 68Q45

Acknowledgements

We sincerely thank the anonymous reviewers for the helpful comments. Much of the work for this paper was carried out while at the IT University of Copenhagen.

Notes

1. Here, the decision whether or not to move-right remains non-deterministic; however, the decision of which move-right step to carry out becomes deterministic.

2. The first argument of δ may technically only be less than the length of the lookahead, when it contains the right sentinel, even though it need only ‘look’ at the first symbol.

3. Recall that all cycles of a computation for a monotone restarting automata are monotone, no matter if they lead to accepting the input or not.

4. In fact, marking the last symbol of u_i+1 is not necessary, but it makes the simulation easier to visualize.

5. Note that this is, in fact, only a small improvement on the fact that -RWWRRWW(1)) for all (right–left-, left-)mon-,, which is an immediate consequence of results in [4].

6. This is not the shortest rule set possible for this language; the use of different work-tape symbols helps the exposition of the example – there is a new work-tape symbol for each cycle on input a⁸.

7. At the appropriate time t in the computation, .

8. By prefix in a right-computation we mean the prefix of the segment of work-tape contents following the rewrite.