{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T23:41:29Z","timestamp":1767138089739,"version":"build-2238731810"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662391044","type":"print"},{"value":"9783662400876","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1975]]},"DOI":"10.1007\/978-3-662-40087-6_1","type":"book-chapter","created":{"date-parts":[[2013,12,6]],"date-time":"2013-12-06T00:57:18Z","timestamp":1386291438000},"page":"3-51","source":"Crossref","is-referenced-by-count":0,"title":["On the Structure of Feasible Computations"],"prefix":"10.1007","author":[{"given":"J.","family":"Hartmanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Simon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","volume-title":"The design and analysis of computer algorithms. Addison-Wesley","author":"A Aho","year":"1974","unstructured":"Aho, A., J.E. Hoperoft, and J.D. Ullman: The design and analysis of computer algorithms. Addison-Wesley, Reading, Mass. 1974"},{"key":"1_CR2","unstructured":"Baker, T., J. Gill and R. Solovay: Relativization of the P =? NP question. To be published in SICOMP."},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"JR B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second order arithmetic and finite automata. Zeit. f. Math. Log. und Grund. der Math., 6 (1960) 66\u201392.","journal-title":"Zeit. f. Math. Log. und Grund. der Math."},{"key":"1_CR4","unstructured":"B\u00fcchi, J.R. and C.C. Elgot: Decision problems of weak second order arithmetics and finite automata, Part I. AMS Notices, 5 (1959) Abstract 834."},{"key":"1_CR5","first-page":"75","volume-title":"Linear time simulation of deterministic two-way pushdown automata. Information Processing71","author":"S Cook","year":"1972","unstructured":"Cook, S.: Linear time simulation of deterministic two-way pushdown automata. Information Processing 71. North Holland, Amsterdam 1972. 75\u201380."},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Cook, S.: The complexity of theorem-proving procedures. Proc. 3rd Ann. ACM Symp. Th. Comp. 1971 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"1_CR7","unstructured":"Fisher, M.J. and M.O. Rabin: Super-exponential complexity of Pressburger arithmetic. Project MAC TM 43 (1974)"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S Greibach","year":"1973","unstructured":"Greibach, S.: The hardest context-free language. SIAM J. Como. v. 2, (1973) 304\u2013310.","journal-title":"SIAM J. Como"},{"key":"1_CR9","volume-title":"The lba problem and its importance in the theory of computing. TR-171 Dept. Comp. Sci","author":"J Hartmanis","year":"1973","unstructured":"Hartmanis, J. and H.B. Hunt III: The lba problem and its importance in the theory of computing. TR-171 Dept. Comp. Sci. Cornell University (1973). To be published by the AMS."},{"key":"1_CR10","first-page":"125","volume":"3","author":"J Hartmanis","year":"1969","unstructured":"Hartmanis, J. and H. Shank: Two memory bounds for the recognition of primes by automata. MST v. 3 (1969) 125\u2013129.","journal-title":"MST"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/321466.321470","volume":"15","author":"J Hartmanis","year":"1968","unstructured":"Hartmanis, J. and H. Shank: On the recognition of primes by automata. JACM v. 15 (1968) 382\u2013389.","journal-title":"JACM"},{"key":"1_CR12","volume-title":"Conf. Rec. IEEE 15th SWAT","author":"J Hartmanis","year":"1974","unstructured":"Hartmanis, J. and J. Simon: On the power of multiplication in random access machines. Conf. Rec. IEEE 15th SWAT (1974)."},{"key":"1_CR13","volume-title":"Formal languages and their relation to automata. Addison-Wesley","author":"JE Hoperoft","year":"1969","unstructured":"Hoperoft, J.E. and J.D. Ullman: Formal languages and their relation to automata. Addison-Wesley, Reading, Mass. 1969."},{"key":"1_CR14","volume-title":"On time and tape complexity of languages. Ph.D. Dissertation","author":"HBIII Hunt","year":"1973","unstructured":"Hunt, H.B. III: On time and tape complexity of languages. Ph.D. Dissertation, 1973, Cornell University, Ithaca, N.Y."},{"key":"1_CR15","unstructured":"Hunt, H.B. III: On time and tape complexity of languages. 5th Ann. ACM Symp. Th. Comp. (1973) 10\u201319."},{"key":"1_CR16","unstructured":"Karp, R.: Reducibilities among combinatorial problems. R. Miller and J. Thatcher (eds), Complexity of Computer Computations. Plenum Press (1972) 85\u2013104."},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/S0019-9958(64)90120-2","volume":"3","author":"SY Kuroda","year":"1964","unstructured":"Kuroda, S.Y.: Classes of languages and linear bounded automata. Information and Control v. 3 (1964) 207\u2013223.","journal-title":"Information and Control"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0019-9958(63)90169-4","volume":"2","author":"PS Landweber","year":"1963","unstructured":"Landweber, P.S.: Three theorems on phrase structure grammars of type 1. Information and Control v. 2 (1963) 131\u2013136.","journal-title":"Information and Control"},{"key":"1_CR19","volume-title":"Regular expressions and state graphs. E.F. Moore (ed) Sequential Machines: Selected Papers. Addison-Wesley","author":"R Mcnaughton","year":"1964","unstructured":"McNaughton, R. and H. Yamada: Regular expressions and state graphs. E.F. Moore (ed) Sequential Machines: Selected Papers. Addison-Wesley, Reading, Mass. 1964."},{"key":"1_CR20","unstructured":"Meyer, A.: Weak monadic second order theory of successor is not elementary recursive. M.I.T. Project MAC TM 38(1973)."},{"key":"1_CR21","unstructured":"Meyer, A. and L. Stockmeyer: The equivalence problem for regular expressions with squaring requires exponential space, Conf. Rec. IEEE 13th SWAT (1972) 125\u2013129."},{"key":"1_CR22","unstructured":"Meyer, A. and L. Stockmeyer: Word problems requiring exponential tape. Proc. 5th Ann. ACM Symp. Th. Comp. (1973) 1\u20139."},{"issue":"2","key":"1_CR23","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1145\/321574.321575","volume":"17","author":"M Minsky","year":"1970","unstructured":"Minsky, M.: Form and content in computer science. JACM v. 17 n. 2 (1970) 197\u2013215.","journal-title":"JACM"},{"key":"1_CR24","unstructured":"Myhill, J.: Linearly bounded automata. WADD Technical Note 60\u2013165 (June 1960)."},{"key":"1_CR25","unstructured":"Oppen, D.C.: Elementary bounds for Pressburger arithmetic. Proc. 5th Ann. ACM Symp. Th. Comp. (1973) 34\u201337."},{"key":"1_CR26","volume-title":"Unpublished manuscript","author":"VR Pratt","year":"1974","unstructured":"Pratt, V.R.: Every prime has a succinct certification. Unpublished manuscript (January 1974)."},{"key":"1_CR27","unstructured":"Pratt, V., L. Stockmeyer and M.O. Rabin: A characterization of the power of vector machines. Proc. 6th Ann. ACM Symp. Th. Comp. (1974) 122\u2013134."},{"key":"1_CR28","volume-title":"Warsaw","author":"M Pressburger","year":"1929","unstructured":"Pressburger, M.: \u00dcber die Vollstandigkeit eines gewissen System der Arithmetik ganzen Zahlen, in welchen die Addition als einzige Operation hervortritt. Comptes-Rendus du I Congres des Mathematiciens des Pays Slays. Warsaw, 1929."},{"key":"1_CR29","volume-title":"Conf. Rec. IEEE 15th SWAT","author":"JL Rangel","year":"1974","unstructured":"Rangel, J.L.: The equivalence problem for regular expressions over one letter alphabet is elementary. Conf. Rec. IEEE 15th SWAT (1974)"},{"key":"1_CR30","volume-title":"Theory of recursive functions and effective computability","author":"H Rogers Jr","year":"1967","unstructured":"Rogers, H. Jr.: Theory of recursive functions and effective computability. McGraw-Hill, New York. 1967."},{"key":"1_CR31","first-page":"177","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relations between nondeterministic and deterministic tape complexities. JCSS v. 4 (1970) 177\u2013192.","journal-title":"JCSS"},{"key":"1_CR32","volume-title":"Cornell University","author":"J Simon","year":"1974","unstructured":"Simon, J.: On the power of multiplication in random access ma-chines. TR 74\u2013205 Dept. of Comp. Sci. Cornell University (1974)."},{"key":"1_CR33","unstructured":"Stearns, R.E., J. Hartmanis and P.M. Lewis: Hierarchies of memory limited computations. Conf. Rec. IEEE 6th SWAT (1965) 179\u2013190."},{"key":"1_CR34","unstructured":"Stockmeyer, L.J.: The complexity of decision problems in automata theory and logic. Project MAC TR 133 (July 1974)."}],"container-title":["Lecture Notes in Computer Science","GI-4.Jahrestagung"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-40087-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,4]],"date-time":"2019-08-04T10:38:40Z","timestamp":1564915120000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-40087-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975]]},"ISBN":["9783662391044","9783662400876"],"references-count":34,"aliases":["10.1007\/3-540-07141-5_208"],"URL":"https:\/\/doi.org\/10.1007\/978-3-662-40087-6_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1975]]}}}