On tape-bounded complexity classes and multihead finite automata

摘要

The principal result described in this paper is the equivalence of the following statements:o(1)Every set accepted by a nondeterministic one-way two-head finite automaton can be accepted by a deterministic two-way k-head finite automaton, for some k.(2)The context-free language Lp (described in the paper) is recognized by a deterministic (log n)-tape bounded Turing machine.(3)Every set accepted by a nondeterministic (off-line) L(n)-tape bounded Turing machine is accepted by a deterministic (off-line) L(n)-tape bounded Turing machine, provided L(n)≥log n.The language Lp is accepted, in fact, by a nondeterministic pushdown automaton using a single pushdown store symbol (a nondeterministic one-counter automaton) and by a nondeterministic on-line (log n)-tape bounded Turing machine.