One-tape Turing Machines with tape limited to cells initially containing input, which can rewrite each cell on its first
Accepting power
- When
acceptors of Regular Languages, both in the nondeterministic and deterministic variants (2{N/D}FA]] when , 2NFA/2DFA when ) - When
- in the nondeterministic case, acceptors of Context-Free Languages
- in the deterministic case they form a fine-grained hierarchy where D2-LA recognize Deterministic Context-Free languages and for any
, there is a language recognized by a D -LA that cannot be recognized by a D -LA
- It is part of our current work to prove (and find the complexity tradeoffs) that sweeping
-limited automata are acceptors of Regular Languages