{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T18:22:38Z","timestamp":1782670958518,"version":"3.54.5"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1972,1,1]],"date-time":"1972-01-01T00:00:00Z","timestamp":63072000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1972]]},"DOI":"10.1007\/bf00289513","type":"journal-article","created":{"date-parts":[[2004,10,5]],"date-time":"2004-10-05T04:01:52Z","timestamp":1096948912000},"page":"336-344","source":"Crossref","is-referenced-by-count":88,"title":["On non-determinancy in simple computing devices"],"prefix":"10.1007","volume":"1","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The mathematical theory of context-free languages","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S.: The mathematical theory of context-free languages. New York: McGraw-Hill 1966."},{"key":"CR2","volume-title":"Formal languages and their relation to automata","author":"J. E. Hopcroft","year":"1969","unstructured":"Hopcroft, J. E., Ullman, J. D.: Formal languages and their relation to automata. Addison-Wesley, Reading, Mass., 1969."},{"key":"CR3","volume-title":"Doctorial thesis","author":"W. J. Savitch","year":"1969","unstructured":"Savitch, W. J.: Nondederministic tape-bounded Turing machines: Doctorial thesis, Univ. of Calif., Berkeley, Calif., 1969."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"Hartmanis, J., Lewis II, P. M., Stearns, R. E.: Hierarchies of memory limited computations. IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan, p. 179?190, 1965.","DOI":"10.1109\/FOCS.1965.11"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"F. C. Hennie","year":"1966","unstructured":"Hennie, F. C., Stearns, R. E.: Two-tape simulation of multi-tape Turing machines. JACM 13, 533?546 (1966).","journal-title":"JACM"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF02759719","volume":"1","author":"M. O. Rabin","year":"1964","unstructured":"Rabin, M. O.: Real time computation. Israel J. Math. 1, 203?211 (1964).","journal-title":"Israel J. Math."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1145\/321650.321661","volume":"18","author":"J. Hartmanis","year":"1971","unstructured":"Hartmanis, J., Hopcroft, J. E.: An overview of the theory of computational complexity. JACM 18, 444?475 (1971).","journal-title":"JACM"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R. E.: On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 285?306 (1965).","journal-title":"Trans. Amer. Math. Soc."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01694180","volume":"5","author":"J. Hartmanis","year":"1971","unstructured":"Hartmanis, J.: Computational complexity of random access stored program machines. J. Math. Systems Theory 5, 232?245 (1971).","journal-title":"J. Math. Systems Theory"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00289513.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00289513\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00289513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T21:34:49Z","timestamp":1734557689000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00289513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1972]]},"references-count":9,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1972]]}},"alternative-id":["BF00289513"],"URL":"https:\/\/doi.org\/10.1007\/bf00289513","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1972]]}}}