A Note Concerning Nondeterministic Tape Complexities
- 1 October 1972
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 19 (4) , 608-612
- https://doi.org/10.1145/321724.321727
Abstract
A set of sufficient conditions on tape functions Ll(n) and L2(n) is presented that guarantees the existence of a set accepted by an Ll(n)-tape bounded nondeterministic Turing machine, but not accepted by any L~(n)-tape bounded nondeterministic Turing machine. In- teresting corollaries arise. For example, it is shown that, for integers m >_ 0, p > 1, and q > 1, there is a set accepted by an (n~+(P/q))-tape bounded nondeterministic Turing machine that is not accepted by any (nm+(p/(q+l)))-tape bounded nondeterministic Turing machine.Keywords
This publication has 6 references indexed in Scilit:
- A note on AFLs and bounded erasingInformation and Control, 1971
- Characterizations of some tape and time complexity classes of turing machines in terms of multihead and auxiliary stack automataJournal of Computer and System Sciences, 1971
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970
- Some Results on Tape-Bounded Turing MachinesJournal of the ACM, 1969
- Nonerasing stack automataJournal of Computer and System Sciences, 1967
- Stack automata and compilingJournal of the ACM, 1967