{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:43:02Z","timestamp":1725601382011},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540068594"},{"type":"electronic","value":"9783540378198"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1974]]},"DOI":"10.1007\/3-540-06859-7_138","type":"book-chapter","created":{"date-parts":[[2011,8,18]],"date-time":"2011-08-18T15:52:56Z","timestamp":1313682776000},"page":"253-265","source":"Crossref","is-referenced-by-count":0,"title":["Non-existence of program optimizers in an abstract setting"],"prefix":"10.1007","author":[{"given":"Donald A.","family":"Alton","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John L.","family":"Lowther","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"20_CR1","unstructured":"Alton, D. A., Diversity of speedups and embeddability in computational complexity, Tech. Rep. 73-01, Dept. of Computer Science, Univ. of Iowa, available as Report NSF-OCA-GJ-33168-01 (accession no. PB-221089) from National Technical Information Service, U.S. Dept. of Commerce, Springfield, Va. 22151, to appear in shorter version, J. of Symbolic Logic."},{"key":"20_CR2","unstructured":"\u2014, Non-existence of program optimizers in an abstract setting, Tech. Rep. 73-08, Dept. of Computer Science, Univ. of Iowa, available as Report NSF-OCA-GJ-33168-02 (accession number PB-226 464\/AS) from National Technical Information Service, U.S. Dept. of Commerce, Springfield, Va. 22151."},{"key":"20_CR3","unstructured":"\u2014, revision of [2], to appear, J. Comput. System Sci."},{"key":"20_CR4","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, J. Assoc. Comput. Mach. 14, 322\u2013336 (1967).","journal-title":"J. Assoc. Comput. Mach."},{"key":"20_CR5","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1145\/321637.321648","volume":"18","author":"M. Blum","year":"1971","unstructured":"\u2014, On effective procedures for speeding up algorithms, J. Assoc. Comput. Mach. 18, 290\u2013305 (1971).","journal-title":"J. Assoc. Comput. Mach."},{"key":"20_CR6","unstructured":"Cobham, A., The intrinsic computational difficulty of functions, in Logic, Methodology, and Philosophy of Science (Proc. 1964 Internat. Conf., ed. Bar-Hillel, North Holland, 1965), 24\u201330."},{"key":"20_CR7","first-page":"37","volume-title":"Computational Complexity (Courant Comp. Sci. Symp. 7","author":"R. Constable","year":"1973","unstructured":"Constable, R., Two types of hierarchy theorems for axiomatic complexity classes, in Computational Complexity (Courant Comp. Sci. Symp. 7, ed. Rustin, Algorithmics Press, New York, 1973), 37\u201363."},{"key":"20_CR8","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/321707.321721","volume":"19","author":"R. Constable","year":"1972","unstructured":"\u2014 and Borodin, A., Subrecursive programming languages 1: efficiency and program structure, J. Assoc. Comput. Mach. 19, 526\u2013568 (1972).","journal-title":"J. Assoc. Comput. Mach."},{"key":"20_CR9","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S. Cook","year":"1973","unstructured":"Cook, S., and Reckhow, R., Time bounded random access machines, J. Comput. System Sci. 7, 354\u2013375 (1973).","journal-title":"J. Comput. System Sci."},{"key":"20_CR10","unstructured":"Grzegorczyk, A., Some classes of recursive functions, Rozprawy Mat. 4 (1953)."},{"key":"20_CR11","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, Math. Systems Theory 5, 232\u2013245 (1971).","journal-title":"Math. Systems Theory"},{"key":"20_CR12","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1145\/321650.321661","volume":"18","author":"J. Hartmanis","year":"1971","unstructured":"\u2014 and Hopcroft, J., An overview of the theory of computational complexity, J. Assoc. Comput. Mach. 18, 444\u2013475 (1971).","journal-title":"J. Assoc. Comput. Mach."},{"key":"20_CR13","unstructured":"Lowther, J., The existence and non-existence of optimizers for subrecursive programming languages, Ph.D. dissertation, The University of Iowa, in preparation."},{"key":"20_CR14","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1090\/S0002-9947-1963-0158822-2","volume":"106","author":"R. Ritchie","year":"1963","unstructured":"Ritchie, R., Classes of predictably computable functions, Trans. Amer. Math. Soc. 106, 139\u2013173 (1963).","journal-title":"Trans. Amer. Math. Soc."},{"key":"20_CR15","unstructured":"Rogers, R., Theory of recursive functions and effective computability, McGraw-Hill, 1967."}],"container-title":["Lecture Notes in Computer Science","Programming Symposium"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-06859-7_138.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:43:37Z","timestamp":1619556217000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-06859-7_138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974]]},"ISBN":["9783540068594","9783540378198"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-06859-7_138","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1974]]}}}