{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:01:03Z","timestamp":1725858063513},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319401881"},{"type":"electronic","value":"9783319401898"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40189-8_25","type":"book-chapter","created":{"date-parts":[[2016,6,13]],"date-time":"2016-06-13T11:34:07Z","timestamp":1465817647000},"page":"240-250","source":"Crossref","is-referenced-by-count":1,"title":["Program Size Complexity of Correction Grammars in the Ershov Hierarchy"],"prefix":"10.1007","author":[{"given":"John","family":"Case","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James S.","family":"Royer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,14]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1002\/malq.19960420138","volume":"42","author":"C Ash","year":"1996","unstructured":"Ash, C., Knight, J.: Recursive structures and Eshov\u2019s hierarchy. Math. Logic Q. 42, 461\u2013468 (1996)","journal-title":"Math. Logic Q."},{"key":"25_CR2","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0019-9958(67)90546-3","volume":"11","author":"M Blum","year":"1967","unstructured":"Blum, M.: On the size of machines. Inf. Control 11, 257\u2013265 (1967)","journal-title":"Inf. Control"},{"key":"25_CR3","volume-title":"Currents in the Theory of Computing","author":"A Borodin","year":"1973","unstructured":"Borodin, A.: Computational complexity: Theory and practice. In: Aho, A.V. (ed.) Currents in the Theory of Computing. Prentice-Hall, Englewood Cliffs (1973)"},{"key":"25_CR4","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0168-0072(94)00056-9","volume":"75","author":"W Buchholz","year":"1995","unstructured":"Buchholz, W.: Proof-theoretic analysis of termination proofs. Ann. Pure Appl. Logic 75, 57\u201365 (1995)","journal-title":"Ann. Pure Appl. Logic"},{"key":"25_CR5","unstructured":"Burgin, M.: Grammars with prohibition and human-computer interaction. In: Proceedings of the Business and Industry Simulation Symposium, pp. 143\u2013147. Society for Modeling and Simulation International (2005)"},{"key":"25_CR6","doi-asserted-by":"crossref","first-page":"489","DOI":"10.2178\/jsl\/1243948324","volume":"74","author":"L Carlucci","year":"2009","unstructured":"Carlucci, L., Case, J., Jain, S.: Learning correction grammars. J. Symb. Logic 74, 489\u2013516 (2009)","journal-title":"J. Symb. Logic"},{"issue":"5","key":"25_CR7","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1002\/malq.201020054","volume":"57","author":"J Case","year":"2011","unstructured":"Case, J., Jain, S.: Rice and Rice-Shapiro theorems for transfinite correction grammars. Math. Logic Q. 57(5), 504\u2013516 (2011)","journal-title":"Math. Logic Q."},{"key":"25_CR8","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0022-0000(71)80039-9","volume":"5","author":"R Constable","year":"1971","unstructured":"Constable, R.: Subrecursive programming languages II: on program size. J. Comput. Syst. Sci. 5, 315\u2013334 (1971)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"30","DOI":"10.2307\/2266324","volume":"18","author":"W Craig","year":"1953","unstructured":"Craig, W.: On axiomatizability within a system. J. Symb. Logic 18, 30\u201332 (1953)","journal-title":"J. Symb. Logic"},{"key":"25_CR10","unstructured":"Drumm, E.: Extensions to blum\u2019s size results in subrecursive formalisms. Master\u2019s thesis, University of Toronto (1970)"},{"key":"25_CR11","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BFb0090937","volume-title":"Logic Year 1979\u201380","author":"RL Epstein","year":"1981","unstructured":"Epstein, R.L., Haas, R., Kramer, R.L.: Hierarchies of sets and degrees below $$\\mathbf{0}^{\\prime }$$ 0 \u2032 . In: Lerman, M., Schmerl, J.H., Soare, R.I. (eds.) Logic Year 1979\u201380. Lecture Notes in Mathematics, vol. 859, pp. 32\u201348. Springer, Heidelberg (1981)"},{"key":"25_CR12","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02218750","volume":"7","author":"YL Ershov","year":"1968","unstructured":"Ershov, Y.L.: A hierarchy of sets. I. Algebra Logic 7, 25\u201343 (1968)","journal-title":"I. Algebra Logic"},{"key":"25_CR13","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/BF02218664","volume":"7","author":"YL Ershov","year":"1968","unstructured":"Ershov, Y.L.: A hierarchy of sets II. Algebra Logic 7, 212\u2013284 (1968)","journal-title":"Algebra Logic"},{"key":"25_CR14","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/BF02219847","volume":"9","author":"YL Ershov","year":"1970","unstructured":"Ershov, Y.L.: A hierarchy of sets III. Algebra Logic 9, 20\u201331 (1970)","journal-title":"Algebra Logic"},{"issue":"2","key":"25_CR15","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1006\/inco.1993.1068","volume":"107","author":"R Freivalds","year":"1993","unstructured":"Freivalds, R., Smith, C.: On the role of procrastination in machine learning. Inf. Comput. 107(2), 237\u2013271 (1993)","journal-title":"Inf. Comput."},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1137\/0209010","volume":"9","author":"J Hartmanis","year":"1980","unstructured":"Hartmanis, J.: On the succinctness of different representations of languages. SIAM J. Comput. 9, 114\u2013120 (1980)","journal-title":"SIAM J. Comput."},{"key":"25_CR17","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(83)90016-6","volume":"26","author":"J Hartmanis","year":"1983","unstructured":"Hartmanis, J.: On G\u00f6del speed-up and succinctness of language representations. Theor. Comput. Sci. 26, 335\u2013342 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"25_CR18","doi-asserted-by":"crossref","first-page":"352","DOI":"10.4153\/CJM-1975-043-4","volume":"27","author":"L Hay","year":"1975","unstructured":"Hay, L.: Rice theorems for d.r.e. sets. Can. J. Math 27, 352\u2013365 (1975)","journal-title":"Can. J. Math"},{"key":"25_CR19","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(82)80081-8","volume":"52","author":"L Hay","year":"1982","unstructured":"Hay, L.: On the recursion-theoretic complexity of relative succinctness of representations of languages. Inf. Control 52, 2\u20137 (1982)","journal-title":"Inf. Control"},{"key":"25_CR20","volume-title":"Introduction to Automata Theory Languages and Computation","author":"J Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory Languages and Computation. Addison-Wesley, Reading (1979)"},{"key":"25_CR21","doi-asserted-by":"crossref","first-page":"150","DOI":"10.2307\/2267778","volume":"3","author":"SC Kleene","year":"1938","unstructured":"Kleene, S.C.: On notation for ordinal numbers. J. Symb. Logic 3, 150\u2013155 (1938)","journal-title":"J. Symb. Logic"},{"key":"25_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-49820-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M Li","year":"2008","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, New York (2008)","edition":"3"},{"key":"25_CR23","volume-title":"Introduction to Mathematical Logic","author":"E Mendelson","year":"2009","unstructured":"Mendelson, E.: Introduction to Mathematical Logic, 5th edn. Chapman & Hall, New York (2009)","edition":"5"},{"key":"25_CR24","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/S0019-9958(72)90592-X","volume":"21","author":"A Meyer","year":"1972","unstructured":"Meyer, A.: Program size in restricted programming languages. Inf. Control 21, 382\u2013394 (1972)","journal-title":"Inf. Control"},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"Meyer, A., Bagchi, A.: Program size and economy of description. In: Proceedings of the 4th Annual ACM Symposium on Theory of Computing, pp. 183\u2013186 (1972)","DOI":"10.1145\/800152.804912"},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"Meyer, A., Fischer, M.: Economy of description by automata, grammars and formal systems. In: Proceedings of the IEEE 12th Annual Symposium on Switching and Automata Theory, pp. 42\u201351 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"Meyer, A., Ritchie, D.: The complexity of loop programs. In: Proceedings of the 22nd National ACM Conference, pp. 465\u2013469. Thomas Book Co. (1967)","DOI":"10.1145\/800196.806014"},{"key":"25_CR28","volume-title":"Recursive Functions","author":"R P\u00e9ter","year":"1967","unstructured":"P\u00e9ter, R.: Recursive Functions. Academic Press, New York (1967)"},{"key":"25_CR29","series-title":"London Mathematical Society Lecture Note Series","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1017\/CBO9781107325944.011","volume-title":"Sets and Proofs","author":"M Rathjen","year":"1999","unstructured":"Rathjen, M.: The realm of ordinal analysis. In: Cooper, S., Truss, J. (eds.) Sets and Proofs. London Mathematical Society Lecture Note Series, vol. 258, pp. 219\u2013279. Cambridge University Press, Cambridge (1999)"},{"key":"25_CR30","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H Rogers","year":"1967","unstructured":"Rogers, H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967). Reprinted by MIT Press, 1987"},{"key":"25_CR31","unstructured":"Royer, J., Case, J.: Subrecursive Programming Systems: Complexity & Succinctness. Monograph in Programming Theoretical Computer Science. Birkh\u00e4user, Boston (1994). See www.cis.udel.edu\/~case\/RC94Errata.pdf for corrected errata"},{"key":"25_CR32","volume-title":"Degrees of Unsolvability","author":"G Sacks","year":"1963","unstructured":"Sacks, G.: Degrees of Unsolvability. Princeton University Press, Princeton (1963)"},{"key":"25_CR33","first-page":"547","volume":"32","author":"E Schmidt","year":"1976","unstructured":"Schmidt, E., Szymanski, T.: Succinctness of descriptions of ambiguous context-free languages. Inf. Control 32, 547\u2013553 (1976)","journal-title":"Inf. Control"},{"key":"25_CR34","volume-title":"Subsystems of Second Order Arithmetic","author":"S Simpson","year":"2010","unstructured":"Simpson, S.: Subsystems of Second Order Arithmetic, 2nd edn. Cambridge University Press, Cambridge (2010)","edition":"2"},{"key":"25_CR35","series-title":"Annals of Mathematics Studies","doi-asserted-by":"crossref","DOI":"10.1515\/9781400882007","volume-title":"Theory of Formal Systems","author":"R Smullyan","year":"1961","unstructured":"Smullyan, R.: Theory of Formal Systems. Annals of Mathematics Studies, vol. 47. Princeton University Press, Princeton (1961)"},{"key":"25_CR36","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively Enumerable Sets and Degrees","author":"R Soare","year":"1987","unstructured":"Soare, R.: Recursively Enumerable Sets and Degrees. Springer, Heidelberg (1987)"},{"key":"25_CR37","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1016\/j.apal.2009.01.008","volume":"160","author":"R Soare","year":"2009","unstructured":"Soare, R.: Turing oracle machines, online computing, and three displacements in computability theory. Ann. Pure Appl. Logic 160, 368\u2013399 (2009)","journal-title":"Ann. Pure Appl. Logic"},{"key":"25_CR38","series-title":"Studies in Logic and the Foundations of Mathematics","volume-title":"Proof Theory","author":"G Takeuti","year":"1987","unstructured":"Takeuti, G.: Proof Theory. Studies in Logic and the Foundations of Mathematics, vol. 81, 2nd edn. North-Holland, Amsterdam (1987)","edition":"2"},{"key":"25_CR39","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L Valiant","year":"1976","unstructured":"Valiant, L.: Relative complexity of checking and evaluating. Inf. Process. Lett. 5, 20\u201323 (1976)","journal-title":"Inf. Process. Lett."},{"key":"25_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/BFb0023786","volume-title":"Computer Science Logic","author":"A Weiermann","year":"1992","unstructured":"Weiermann, A.: Proving termination for term rewriting systems. In: B\u00f6rger, E., J\u00e4ger, G., B\u00fcning, H., Richter, M. (eds.) CSL 1991. LNCS, vol. 626, pp. 419\u2013428. Springer, Heidelberg (1992)"}],"container-title":["Lecture Notes in Computer Science","Pursuit of the Universal"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40189-8_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T12:17:31Z","timestamp":1498306651000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40189-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319401881","9783319401898"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40189-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}