On determinism versus non-determinism and related problems
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (02725428) , 429-438
- https://doi.org/10.1109/sfcs.1983.39
Abstract
We show that, for multi-tape Turing machines, non-deterministic linear time is more powerful than deterministic linear time. We also discuss the prospects for extending this result to more general Turing machines.Keywords
This publication has 17 references indexed in Scilit:
- On depth-reduction and gratesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Asymptotically tight bounds on time-space trade-offs in a pebble gameJournal of the ACM, 1982
- A family of graphs with expensive depth-reductionTheoretical Computer Science, 1982
- Probabilistic simulations (Preliminary Version)Published by Association for Computing Machinery (ACM) ,1982
- Advances in pebblingPublished by Springer Nature ,1982
- On time versus space IIJournal of Computer and System Sciences, 1981
- On alternation IIActa Informatica, 1980
- On alternationActa Informatica, 1980
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Memory bounds for recognition of context-free and context-sensitive languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965