Back to Search Start Over

On tape-bounded complexity classes and multi-head finite automata

Authors :
I. H. Sudborough
Source :
SWAT (FOCS)
Publication Year :
1973
Publisher :
IEEE, 1973.

Abstract

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 (log n)-tape bounded deterministic Turing machine. (3) Every set accepted by a L(n)-tape bounded nondeterministic Turing machine is recognized by a L(n)-tape bounded deterministic Turing machine, provided L(n) ≥ log n. This work extends results reported earlier by Hartmanis [2], Savitch [9,10], and Lewis, Stearns, and Hartmanis [6].

Details

Database :
OpenAIRE
Journal :
14th Annual Symposium on Switching and Automata Theory (swat 1973)
Accession number :
edsair.doi...........7e02db947a74dabd6196a90c488eb41b