{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:24:51Z","timestamp":1725686691572},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642308697"},{"type":"electronic","value":"9783642308703"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30870-3_28","type":"book-chapter","created":{"date-parts":[[2012,5,28]],"date-time":"2012-05-28T02:56:12Z","timestamp":1338173772000},"page":"276-282","source":"Crossref","is-referenced-by-count":0,"title":["Turing Machine-Inspired Computer Science Results"],"prefix":"10.1007","author":[{"given":"Juris","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","first-page":"143","volume":"14","author":"Y. Bar-Hillel","year":"1961","unstructured":"Bar-Hillel, Y., Perlis, M., Shamir, E.: On formal properties of simple phrase structure grammars. Z. Phonetik, Sprachwissen. Komm.\u00a014, 143\u2013172 (1961)","journal-title":"Z. Phonetik, Sprachwissen. Komm."},{"issue":"2","key":"28_CR2","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M. Blum","year":"1967","unstructured":"Blum, M.: A machine-independent theory of the complexity of recursive functions. J. Assoc. Comput. Mach.\u00a014(2), 322\u2013336 (1967)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"28_CR3","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1145\/321637.321648","volume":"18","author":"M. Blum","year":"1971","unstructured":"Blum, M.: On effective procedures for speeding up algorithms. J. Assoc. Comput. Mach.\u00a018(2), 290\u2013305 (1971)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"28_CR4","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1145\/321679.321691","volume":"19","author":"A.B. Borodin","year":"1972","unstructured":"Borodin, A.B.: Computational complexity and the existence of complexity gaps. J. Assoc. Comput. Mach.\u00a019(1), 158\u2013174 (1972)","journal-title":"J. Assoc. Comput. Mach."},{"unstructured":"Cocke, J., Schwartz, J.T.: Programming languages and their compilers: Preliminary notes. Tech. rep., Courant Institute (1970)","key":"28_CR5"},{"key":"28_CR6","first-page":"151","volume-title":"Proc. 3rd Symp. Theory of Computing","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proc. 3rd Symp. Theory of Computing, pp. 151\u2013158. ACM, New York (1971)"},{"key":"28_CR7","doi-asserted-by":"publisher","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.\u00a0117, 285\u2013306 (1965)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"4","key":"28_CR8","first-page":"759","volume":"37","author":"J. Hartmanis","year":"1972","unstructured":"Hartmanis, J.: Context-free languages and Turing machine computations. J. Symbolic Logic\u00a037(4), 759 (1972)","journal-title":"J. Symbolic Logic"},{"doi-asserted-by":"crossref","unstructured":"Hartmanis, J., Simon, J.: On the power of multiplciation in random-access machines. In: Proc. 15th Annu. IEEE Sympos. Switching Automata Theory, pp. 13\u201323 (1974)","key":"28_CR9","DOI":"10.1109\/SWAT.1974.20"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complement. SIAM J. Comput.\u00a017, 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"unstructured":"Kasami, T.: An efficient recognition and syntax algorithm for context-free languages. Tech. Rep. AFCRL-65-758, Air Force Cambridge Research Lab (1965)","key":"28_CR11"},{"doi-asserted-by":"crossref","unstructured":"Pratt, V.R., Rabin, M.O., Stockmeyer, L.J.: A characterization of the power of vector machines. In: Proc. ACM Symp. Theory of Computation (STOC 1974), pp. 122\u2013134 (1974)","key":"28_CR12","DOI":"10.1145\/800119.803892"},{"issue":"2","key":"28_CR13","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"Savitch, W.: Relationship between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci.\u00a04(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR14","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"C.E. Shannon","year":"1948","unstructured":"Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal\u00a027, 379\u2013423, 623\u2013656 (1948)","journal-title":"Bell System Technical Journal"},{"doi-asserted-by":"crossref","unstructured":"Stearns, R., Hartmanis, J., Lewis, R.: Hierarchies of memory limited computations. In: Proc. IEEE Conf. Switching Circuit Theory and Logical Design, pp. 179\u2013190 (1965)","key":"28_CR15","DOI":"10.1109\/FOCS.1965.11"},{"key":"28_CR16","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"Szelepcs\u00e9nyi, R.: The method of forcing for nondeterministic automata. Bull. EATCS\u00a033, 96\u2013100 (1987)","journal-title":"Bull. EATCS"},{"key":"28_CR17","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","volume":"42","author":"A.M. Turing","year":"1936","unstructured":"Turing, A.M.: On computable numbers with an application to the Entscheidungsproblem. Proc. London Math. Soc.\u00a042, 230\u2013265 (1936); erratum: Ibid. 43, 544\u2013546 (1937)","journal-title":"Proc. London Math. Soc."},{"issue":"6","key":"28_CR18","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1109\/TEC.1962.5219459","volume":"EC-11","author":"H. Yamada","year":"1962","unstructured":"Yamada, H.: Real-time computation and recursive functions not real-time computable. IEEE Trans. Electronic Computers\u00a0EC-11(6), 753\u2013760 (1962)","journal-title":"IEEE Trans. Electronic Computers"},{"issue":"2","key":"28_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"D.H. Younger","year":"1967","unstructured":"Younger, D.H.: Recognition and parsing of context-free languages in time n\n                3. Information and Control\u00a010(2), 189\u2013208 (1967)","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","How the World Computes"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30870-3_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:32:24Z","timestamp":1620127944000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30870-3_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642308697","9783642308703"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30870-3_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}