On tape-bounded complexity classes and multi-head finite automata
- 1 October 1973
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 138-144
- https://doi.org/10.1109/swat.1973.20
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].Keywords
This publication has 7 references indexed in Scilit:
- On two-way multihead automataJournal of Computer and System Sciences, 1973
- Language recognition by marking automataInformation and Control, 1972
- On non-determinancy in simple computing devicesActa Informatica, 1972
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970
- Multi-tape and multi-head pushdown automataInformation and Control, 1968
- On Multi-Head Finite AutomataIBM Journal of Research and Development, 1966
- Memory bounds for recognition of context-free and context-sensitive languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965