{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:10Z","timestamp":1725662890943},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540073895"},{"type":"electronic","value":"9783540375852"}],"license":[{"start":{"date-parts":[[1975,1,1]],"date-time":"1975-01-01T00:00:00Z","timestamp":157766400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1975]]},"DOI":"10.1007\/3-540-07389-2_179","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:54:48Z","timestamp":1330185288000},"page":"13-29","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Ten years of speedup"],"prefix":"10.1007","author":[{"given":"Peter van Emde","family":"Boas","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,21]]},"reference":[{"key":"2_CR1","volume-title":"Diversity of Speedups and embeddability in computational complexity, Rep. TR 73-01","author":"D. Alton","year":"1973","unstructured":"ALTON, D., Diversity of Speedups and embeddability in computational complexity, Rep. TR 73-01, Dept. Comp. Sci., Univ. of Iowa (Iowa City, 1973)."},{"key":"2_CR2","volume-title":"Non-existence of program optimizers in an abstract setting, Rep. TR 73-08","author":"D. Alton","year":"1973","unstructured":"ALTON, D., Non-existence of program optimizers in an abstract setting, Rep. TR 73-08, Dept. Comp. Sci., Univ. of Iowa (Iowa City, 1973)."},{"key":"2_CR3","first-page":"6","volume-title":"Automata theory","author":"M. A. Arbib","year":"1966","unstructured":"ARBIB, M.A., Speedup theorems and Incompleteness theorems, in Automata theory, (ed. E.R. Caianello), pp. 6\u201324, Academic Press, New York, 1966."},{"key":"2_CR4","first-page":"261","volume-title":"Theories of abstract automata","author":"M. A. Arbib","year":"1969","unstructured":"ARBIB, M.A., Speedup and incompleteness results, in Theories of abstract automata, pp. 261\u2013267, Prentice Hall, New Jersey, 1969."},{"key":"2_CR5","doi-asserted-by":"crossref","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,\nJ. Assoc. Comput. Mach., 14 (1967), 322\u2013336.","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR6","doi-asserted-by":"crossref","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,\nJ. Assoc. Comput. Mach. 18 (1971), 290\u2013305.","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR7","doi-asserted-by":"crossref","first-page":"579","DOI":"10.2307\/2271984","volume":"38","author":"M. Blum","year":"1973","unstructured":"BLUM, M. & I. MARQUES, On complexity properties of recursively enumerable sets,\nJ. Symbolic Logic, 38 (1973), 579\u2013593.","journal-title":"J. Symbolic Logic"},{"unstructured":"CONSTABLE, R.L; & J. HARTMANIS, Complexity of formal translations and speedup results, in proc. 3rd ACM Symp. on theory of Computing (1971), pp. 244\u2013250.","key":"2_CR8"},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1090\/S0002-9904-1971-12696-4","volume":"77","author":"A. Ehrenfeucht","year":"1971","unstructured":"EHRENFEUCHT, A. & J. MYCIELSKI, Abbreviating proofs by adding new axioms,\nBull. Amer. Math. Soc, 77 (1971), 366\u2013367.","journal-title":"Bull. Amer. Math. Soc"},{"unstructured":"FISCHER, M.J. & M.O. RABIN, Super-exponential complexity of Pressburger arithmetic, MAC techn. memo 43, Project MAC. MIT Cambridge Mass. Feb. 1974.","key":"2_CR10"},{"key":"2_CR11","first-page":"23","volume":"7","author":"K. G\u00f6del","year":"1936","unstructured":"G\u00d6DEL, K., \u00dcber die L\u00e4nge der Beweise. Ergebnisse eines Math. Kolloquiums, 7, 23\u201324 (1936). See also in On the lengths of proofs in The Undecidable, (ed. M. Davis), pp. 82\u201383, Raven Press, NY, 1965.","journal-title":"Ergebnisse eines Math. Kolloquiums"},{"unstructured":"HARTMANIS, J., Oral communication, Dec. 1974.","key":"2_CR12"},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1145\/321650.321661","volume":"18","author":"J. Hartmanis","year":"1971","unstructured":"HARTMANIS, J. & J.E. HOPCROFT, An overview of the theory of computational complexity,\nJ. Assoc. Comput. Mach. 18 (1971), 444\u2013475.","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"21","DOI":"10.2307\/2271512","volume":"36","author":"J. P. Helm","year":"1971","unstructured":"HELM, J.P. & P.R. YOUNG, On size versus efficiency for programs admitting speedup,\nJ. Symbolic Logic, 36 (1971), 21\u201327.","journal-title":"J. Symbolic Logic"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1145\/321694.321702","volume":"19","author":"L. H. Landweber","year":"1972","unstructured":"LANDWEBER, L.H. & E.L. ROBERTSON, Recursive properties of abstract complexity classes,\nJ. Assoc. Comput. Mach., 19 (1972), 296\u2013308.","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR16","series-title":"MAC techn. memo","volume-title":"Weak monadic second order theory of successor is not elementary recursive","author":"A. R. Meyer","year":"1973","unstructured":"MEYER, A.R., Weak monadic second order theory of successor is not elementary recursive, MAC techn. memo 38. Project MAC, MIT, Cambridge Mass. 1973."},{"key":"2_CR17","doi-asserted-by":"crossref","first-page":"55","DOI":"10.2307\/2272545","volume":"37","author":"A. R. Meyer","year":"1972","unstructured":"MEYER, A.R. & P.C. FISCHER, Computational speedup by effective operators,\nJ. Symbolic Logic, 37 (1972), 55\u201368.","journal-title":"J. Symbolic Logic"},{"key":"2_CR18","volume-title":"Sentences undecidable in formalized arithmetic","author":"A. Mostowski","year":"1957","unstructured":"MOSTOWSKI, A., Sentences undecidable in formalized arithmetic, North Holland, Amsterdam, 1957."},{"key":"2_CR19","volume-title":"The theory of recursive functions and effective computability","author":"H. Rogers","year":"1967","unstructured":"ROGERS, H., The theory of recursive functions and effective computability, Mc Graw Hill, New York, 1967."},{"key":"2_CR20","first-page":"585","volume-title":"Automata, Languages and Programming","author":"C. P. Schnorr","year":"1973","unstructured":"SCHNORR, C.P., Does computational speedup concern programming?, in Automata, Languages and Programming, (M. Nivat ed.), pp. 585\u2013592, North Holland\/Elsevier, Amsterdam, 1973."},{"unstructured":"SCHNORR, C.P. & G. STUMPF, A characterization of complexity sequences, Tagungsbericht 46\/1972, Algorithmen und Komplexit\u00e4tstheorie, Math. Forschungs-institut Oberwolfach, Nov. 1972.","key":"2_CR21"},{"key":"2_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-94701-7","volume-title":"Rekursive Funktionen und ihre Komplexit\u00e4t","author":"C. P. Schnorr","year":"1974","unstructured":"SCHNORR, C.P., Rekursive Funktionen und ihre Komplexit\u00e4t, Teubner, Stuttgart, 1974."},{"key":"2_CR23","volume-title":"The complexity of decision problems in Automata theory and Logic, Report MAC TR-133","author":"L. J. Stockmeyer","year":"1974","unstructured":"STOCKMEYER, L.J., The complexity of decision problems in Automata theory and Logic, Report MAC TR-133, Project MAC. MIT, Cambridge Mass., July 1974."},{"key":"2_CR24","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01702871","volume":"5","author":"P. Young","year":"1971","unstructured":"YOUNG, P., Speedups by changing the order in which sets are enumerated,\nMath. Systems Theory, 5 (1971), 148\u2013156.","journal-title":"Math. Systems Theory"},{"key":"2_CR25","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1090\/S0002-9939-1973-0312768-7","volume":"37","author":"P. Young","year":"1973","unstructured":"YOUNG, P., Easy constructions in complexity theory: Gap and Speedup theorems,\nProc. Amer. Math. Soc., 37 (1973), 555\u2013563.","journal-title":"Proc. Amer. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1975 4th Symposium, Mari\u00e1nsk\u00e9 L\u00e1zn\u011b, September 1\u20135, 1975"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-07389-2_179","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T12:25:44Z","timestamp":1558268744000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-07389-2_179"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975]]},"ISBN":["9783540073895","9783540375852"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-07389-2_179","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1975]]},"assertion":[{"value":"21 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}