On tape-bounded complexity classes and multihead finite automata

✍ Scribed by I.H. Sudborough

• Publisher: Elsevier Science
• Year: 1975
• Tongue: English
• Weight: 798 KB
• Volume: 10
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(75)80014-6

✦ Synopsis

The principal result described in this paper is the equivalence of the following statements :

(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.