×

Relationships between nondeterministic and deterministic tape complexities. (English) Zbl 0188.33502


PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blum, M., A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach., 14, 322-336 (1967) · Zbl 0155.01503
[2] Cobham, A., The Recognition Problem for the Set of Perfect Squares, (IEEE Conference Record of the Seventh Annual Symposium on Switching and Automata Theory. IEEE Conference Record of the Seventh Annual Symposium on Switching and Automata Theory, Berkeley, Calif. (1966)), 78-87
[3] Hopcroft, J. E.; Ullman, J. D., (Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.) · Zbl 0196.01701
[4] Hopcroft, J. E.; Ullman, J. D., Relations between time and tape complexities, J. Assoc. Comput. Mach., 15, 414-427 (1968) · Zbl 0169.31103
[5] Hopcroft, J. E.; Ullman, J. D., (Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.), 115-119 · Zbl 0196.01701
[6] Hopcroft, J. E.; Ullman, J. D., (Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.), 115-119 · Zbl 0196.01701
[7] Hopcroft, J. E.; Ullman, J. D., (Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.), 162-164 · Zbl 0196.01701
[8] McCreight, E. M.; Meyer, A. R., Classes of Computable Functions Defined by Bounds on Computation: Preliminary Report, (Conference Record of ACM Symposium on Theory of Computing. Conference Record of ACM Symposium on Theory of Computing, Marina del Rey, Calif. (May 1969)), 79-88 · Zbl 1283.03074
[9] Savitch, W. J., Deterministic Simulation of Non-deterministic Turing Machines (Detailed Abstract), (Conference Record of ACM Symposium on Theory of Computing. Conference Record of ACM Symposium on Theory of Computing, Marina del Rey, Calif. (May 1969)), 247-248 · Zbl 1282.68107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.