{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T04:52:56Z","timestamp":1777438376992,"version":"3.51.4"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1971,9,1]],"date-time":"1971-09-01T00:00:00Z","timestamp":52531200000},"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":[[1971,9]]},"DOI":"10.1007\/bf01694180","type":"journal-article","created":{"date-parts":[[2005,5,15]],"date-time":"2005-05-15T06:09:17Z","timestamp":1116137357000},"page":"232-245","source":"Crossref","is-referenced-by-count":29,"title":["Computational complexity of random access stored program machines"],"prefix":"10.1007","volume":"5","author":[{"given":"J.","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01694180_CR1","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1145\/321239.321240","volume":"11","author":"C. C. Elgot","year":"1964","unstructured":"C. C. Elgot andA. Robinson, Random-access stored-program machines, an approach to programming languages,J. Assoc. Comput. Mach. 11 (1964), 365\u2013399.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01694180_CR2","volume-title":"Computational complexity using random access machines, Course Notes","author":"S. A. Cook","year":"1970","unstructured":"S. A. Cook, Computational complexity using random access machines, Course Notes, University of California, Berkeley, 1970."},{"key":"BF01694180_CR3","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis andR. E. Stearns, On the computational complexity of algorithms,Trans. Amer. Math. Soc. 117 (1965), 285\u2013306.","journal-title":"Trans. Amer. Math. Soc."},{"key":"BF01694180_CR4","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1145\/321450.321464","volume":"15","author":"J. Hartmanis","year":"1968","unstructured":"J. Hartmanis, Computational complexity of one-tape Turing machine computations,J. Assoc. Comput. Mach. 15 (1968), 325\u2013339.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01694180_CR5","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0022-0000(68)80027-3","volume":"2","author":"J. Hartmanis","year":"1968","unstructured":"J. Hartmanis, Tape reversal bounded Turing machine computations,J. Comput. System Sci. 2 (1968), 117\u2013135.","journal-title":"J. Comput. System Sci."},{"key":"BF01694180_CR6","unstructured":"P. C. Fischer, J. Hartmanis andM. Blum, \u201cTape Reversal Complexity Hierarchies\u201d, IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, (1968), pp. 373\u2013382."},{"key":"BF01694180_CR7","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF02759719","volume":"1","author":"M. O. Rabin","year":"1964","unstructured":"M. O. Rabin, Real-time computation,Israel J. Math. 1 (1964), 203\u2013211.","journal-title":"Israel J. Math."},{"key":"BF01694180_CR8","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"F. C. Hennie","year":"1965","unstructured":"F. C. Hennie, One-tape, off-line Turing machine computations,Information and Control 8 (1965), 553\u2013578.","journal-title":"Information and Control"},{"key":"BF01694180_CR9","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"F. C. Hennie","year":"1966","unstructured":"F. C. Hennie andR. E. Stearns, Two-tape simulation of multi-tape Turing machines,J. Assoc. Comput. Mach. 13 (1966), 533\u2013546.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01694180_CR10","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M. Blum","year":"1967","unstructured":"M. Blum, A machine-independent theory of the complexity of recursive functions,J. Assoc. Comput. Mach. 14 (1967), 322\u2013336.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01694180_CR11","unstructured":"A. Borodin, \u201cComplexity Classes of Recursive Functions and the Existence of Complexity Gaps\u201d, Conference Record of ACM Symposium on Theory of Computing, 1969, pp. 67\u201378."},{"key":"BF01694180_CR12","doi-asserted-by":"crossref","unstructured":"E. M. McCreight andA. R. Meyer, \u201cClasses of Computable Functions Defined by Bounds on Computation: Preliminary Report\u201d, Conference Record of ACM Symposium on Theory of Computing, 1969, pp. 79\u201388.","DOI":"10.1145\/800169.805423"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01694180.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01694180\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01694180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T10:09:08Z","timestamp":1586254148000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01694180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1971,9]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1971,9]]}},"alternative-id":["BF01694180"],"URL":"https:\/\/doi.org\/10.1007\/bf01694180","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1971,9]]}}}