Savitch, W. J. Relationships between nondeterministic and deterministic tape complexities. (English) Zbl 0188.33502 J. Comput. Syst. Sci. 4, 177-192 (1970). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 5 ReviewsCited in 367 Documents Keywords:languages, automata, networks PDF BibTeX XML Cite \textit{W. J. Savitch}, J. Comput. Syst. Sci. 4, 177--192 (1970; Zbl 0188.33502) Full Text: DOI OpenURL 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, (), 78-87 [3] Hopcroft, J.E.; Ullman, J.D., () [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] Kuroda, S.Y.; Hopcroft, J.E.; Ullman, J.D., Classes of languages and linear-bound automata, (), 7, 115-119, (1964), The relevant material also appears [6] Landweber, P.S.; Hopcroft, J.E.; Ullman, J.D., Three theorems on phrase structure grammars of type 1, (), 6, 115-119, (1963), The relevant material also appears [7] Lewis, P.M.; Stearns, R.E.; Hartmanis, J.; Hopcroft, J.E.; Ullman, J.D., Memory bounds for the recognition of context-free and context-sensitive languages, (), 162-164, The relevant material also appears [8] McCreight, E.M.; Meyer, A.R., Classes of computable functions defined by bounds on computation: preliminary report, (), 79-88 · Zbl 1283.03074 [9] Savitch, W.J., Deterministic simulation of non-deterministic Turing machines (detailed abstract), (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.