One way finite visit automata

AbstractA one-way preset Turing machine with base L is a nondeterministic on-line Turing machine with one working tape preset to a member of L. FINITEREVERSAL(L) (FINITEVISIT (L)) is the class of languages accepted by one-way preset Turing machines with bases in L which are limited to a finite number of reversals (visits). For any full semiAFL L, FINITEREVERSAL (L) is the closure of L under homomorphic replication or, equivalently, the closure of L under iteration of controls on linear context-free grammars while FINITEVISIT (L) is the result of applying controls from L to absolutely parallel grammars or, equivalently, the closure of L under deterministic two-way finite state transductions. If L is a full AFL with L ≠ FINITEVISIT(L), then FINITEREVERSAL(L) ≠ FINITEVISIT(L). In particular, for one-way checking automata, k + 1 reversals are more powerful than k reversals, k + 1 visits are more powerful than k visits, k visits and k + 1 reversals are incomparable and there are languages definable within 3 visits but no finite number of reversals. Finite visit one-way checking automaton languages can be accepted by nondeterministic multitape Turing machines in space log2 n. Results on finite visit checking automata provide another proof that not all context-free languages can be accepted by one-way nonerasing stack automata