{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:23:08Z","timestamp":1775053388661,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1976,12,1]],"date-time":"1976-12-01T00:00:00Z","timestamp":218246400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1976,12]]},"DOI":"10.1007\/bf01683260","type":"journal-article","created":{"date-parts":[[2005,5,13]],"date-time":"2005-05-13T23:29:17Z","timestamp":1116026957000},"page":"19-32","source":"Crossref","is-referenced-by-count":134,"title":["Relativization of questions about log space computability"],"prefix":"10.1007","volume":"10","author":[{"given":"Richard E.","family":"Ladner","sequence":"first","affiliation":[]},{"given":"Nancy A.","family":"Lynch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01683260_CR1","unstructured":"T. Baker, J. Gill, andR. Solovay, Relativizations of the question. To appear inSIAM Journal on Computing."},{"key":"BF01683260_CR2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. A. Cook","year":"1971","unstructured":"S. A. Cook, Characterizations of pushdown machines in terms of time-bounded computers,Journal of the ACM,18 (1971) 4\u201318.","journal-title":"Journal of the ACM"},{"key":"BF01683260_CR3","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The complexity of theorem proving procedures,Proc. Third Annual ACM Symposium on Theory of Computing, 1971 pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"BF01683260_CR4","doi-asserted-by":"crossref","unstructured":"S. A. Cook, An observation on time-storage trade off,Proc. of Fifth Annual ACM Symposium on Theory of Computing, 1973 pp. 29\u201333.","DOI":"10.1145\/800125.804032"},{"key":"BF01683260_CR5","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/BF00289513","volume":"1","author":"J. Hartmanis","year":"1972","unstructured":"J. Hartmanis, On nondeterminacy of simple computing devices,Acta Informatica,1 (1972) 336\u2013344.","journal-title":"Acta Informatica"},{"key":"BF01683260_CR6","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/S0022-0000(67)80013-8","volume":"1","author":"J. E. Hopcroft","year":"1967","unstructured":"J. E. Hopcroft andJ. D. Ullman, Nonerasing stack automata,Journal of Computer and System Sciences,1 (1967) 166\u2013186.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01683260_CR7","volume-title":"Formal Languages and Their Relation to Automata","author":"J. E. Hopcroft","year":"1969","unstructured":"J. E. Hopcroft andJ. D. Ullman,Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Ma. 1969."},{"key":"BF01683260_CR8","volume-title":"Automata, Languages and Programming","author":"P. Hsia","year":"1973","unstructured":"P. Hsia andR. Yeh, Finite automata with marks, inAutomata, Languages and Programming, M. Nivat, editor, American Elsevier, New York 1973."},{"key":"BF01683260_CR9","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. D. Jones","year":"1975","unstructured":"N. D. Jones, Space-bounded reducibility among combinatorial problems,Journal of Computer and System Sciences,11 (1975) 68\u201385.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01683260_CR10","doi-asserted-by":"crossref","unstructured":"N. D. Jones andW. T. Laaser, Complete problems for deterministic polynomial time,Proc. of Sixth Annual ACM Symposium on Theory of Computing, pp. 40\u201346 1974.","DOI":"10.1145\/800119.803883"},{"key":"BF01683260_CR11","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibility among combinatorial problems, inComplexity of Computer Computations, R. Miller and J. Thatcher, editors, Plenum Press, New York 1972."},{"key":"BF01683260_CR12","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, On the structure of polynomial time reducibility,Journal of the ACM,22 (1975) 155\u2013171.","journal-title":"Journal of the ACM"},{"key":"BF01683260_CR13","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, The circuit value problem is log space complete for ,SIGACT News,7 (1975) 18\u201320.","journal-title":"SIGACT News"},{"key":"BF01683260_CR14","unstructured":"R. E. Ladner, N. A. Lynch, andA. L. Selman, A comparison of polynomial time reducibilities. To appear inTheoretical Computer Science."},{"key":"BF01683260_CR15","unstructured":"N. A. Lynch, Log space recognition and translation of parenthesis languages, manuscript."},{"key":"BF01683260_CR16","unstructured":"N. A. Lynch, Log space machines with multiple oracle tapes, manuscript."},{"key":"BF01683260_CR17","unstructured":"A. R. Meyer, private communication."},{"key":"BF01683260_CR18","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W. J. Savitch, Relationship between nondeterministic and deterministic tape complexities,Journal of Computer and System Sciences,4 (1970) 177\u2013192.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF01683260_CR19","unstructured":"Simon, Istvan. Private communication (Ph.D. Thesis in preparation, Stanford)."},{"key":"BF01683260_CR20","doi-asserted-by":"crossref","unstructured":"R. E. Stearns, J. Hartmanis, andP. M. Lewis II, Hierarchies of memory limited computations,IEEE Conf. Record on Switching Circuit Theory and Logical Design, (1965) 191\u2013202","DOI":"10.1109\/FOCS.1965.11"},{"key":"BF01683260_CR21","unstructured":"L. Stockmeyer andA. R. Meyer, Word problems requiring exponential timeProc. of Fifth Annual ACM Symposium on Theory of Computing, (1973) pp. 1\u20139."},{"key":"BF01683260_CR22","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","volume":"10","author":"I. H. Sudborough","year":"1975","unstructured":"I. H. Sudborough, On tape-bounded complexity classes and multihead automata,Journal of Computer and System Sciences, Vol,10 (1975) 62\u201376.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01683260.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01683260\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01683260","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T09:51:34Z","timestamp":1586253094000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01683260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1976,12]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1976,12]]}},"alternative-id":["BF01683260"],"URL":"https:\/\/doi.org\/10.1007\/bf01683260","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1976,12]]}}}