Multitape finite automata with rewind instructions

摘要

The model of multitape finite automaton is generalized by allowing the automaton to rewind all its tapes simultaneously at any stage in its computation. This added capability is shown to yeild the Boolean closure of the class of word relations defined by multitape finite automata. Several properties of this extended model are investigated. In particular it is shown that this model is incomparable to the nondeterministic multitape finite automata and is strictly weaker than two-way multitape finite automata.