{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,14]],"date-time":"2024-08-14T14:36:37Z","timestamp":1723646197179},"reference-count":46,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":1745,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate a new paradigm in the context of learning in the limit, namely, learning<jats:italic>correction grammars<\/jats:italic>for classes of<jats:italic>computably enumerable (c.e.)<\/jats:italic>languages. Knowing a language may feature a representation of it in terms of<jats:italic>two<\/jats:italic>grammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars<jats:italic>correction grammars<\/jats:italic>. Correction grammars capture the observable fact that people<jats:italic>do<\/jats:italic>correct their linguistic utterances during their usual linguistic activities.<\/jats:p><jats:p>We show that learning correction grammars for classes of c.e. languages in the<jats:bold><jats:italic>TxtEx-mode<\/jats:italic><\/jats:bold>(i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in the<jats:bold><jats:italic>TxtBc<\/jats:italic><\/jats:bold>-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each<jats:italic>n<\/jats:italic>\u2265 0. there is a similar learning advantage, again in learning correction grammars for classes of c.e. languages, but where we compare learning correction grammars that make<jats:italic>n<\/jats:italic>+ 1 corrections to those that make<jats:italic>n<\/jats:italic>corrections.<\/jats:p><jats:p>The concept of a correction grammar can be extended into the constructive transfinite, using the idea of counting-down from notations for transfinite constructive ordinals. This transfinite extension can also be conceptualized as being about learning Ershov-descriptions for c.e. languages. For<jats:italic>u<\/jats:italic>a notation in Kleene's general system (<jats:italic>O<\/jats:italic>, &lt;<jats:sub><jats:italic>o<\/jats:italic><\/jats:sub>) of ordinal notations for constructive ordinals, we introduce the concept of an<jats:italic>u<\/jats:italic>-correction grammar, where<jats:italic>u<\/jats:italic>is used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: if<jats:italic>u<\/jats:italic>and<jats:italic>v<\/jats:italic>are notations for constructive ordinals such that<jats:italic>u<\/jats:italic>&lt;<jats:sub><jats:italic>o<\/jats:italic><\/jats:sub><jats:italic>v<\/jats:italic>. then there are classes of c.e. languages that can be<jats:bold><jats:italic>TxtEx<\/jats:italic><\/jats:bold>-learned by conjecturing<jats:italic>v<\/jats:italic>-correction grammars but not by conjecturing<jats:italic>u<\/jats:italic>-correction grammars.<\/jats:p><jats:p>Surprisingly, we show that\u2014above \u201c<jats:italic>\u03c9<\/jats:italic>-many\u201d corrections\u2014it is not possible to strengthen the hierarchy:<jats:bold><jats:italic>TxtEx<\/jats:italic><\/jats:bold>-learning<jats:italic>u<\/jats:italic>-correction grammars of classes of c.e. languages, where<jats:italic>u<\/jats:italic>is a notation in<jats:italic>O<\/jats:italic>for<jats:italic>any<\/jats:italic>ordinal, can be simulated by<jats:italic>TxtBc<\/jats:italic>-learning<jats:italic>w<\/jats:italic>-correction grammars, where<jats:italic>w<\/jats:italic>is any notation for the smallest infinite ordinal<jats:italic>\u03c9<\/jats:italic>.<\/jats:p>","DOI":"10.2178\/jsl\/1243948324","type":"journal-article","created":{"date-parts":[[2009,6,2]],"date-time":"2009-06-02T13:12:25Z","timestamp":1243948345000},"page":"489-516","source":"Crossref","is-referenced-by-count":6,"title":["Learning correction grammars"],"prefix":"10.1017","volume":"74","author":[{"given":"Lorenzo","family":"Carlucci","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Case","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjay","family":"Jain","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200003534_ref004","first-page":"486","volume":"59","author":"Baliga","year":"1994","journal-title":"Machine learning of higher order programs"},{"key":"S0022481200003534_ref039","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325944.011"},{"key":"S0022481200003534_ref046","volume-title":"Formal Principles of Language Acquisition","author":"Wexler","year":"1980"},{"key":"S0022481200003534_ref001","first-page":"287","volume":"69","author":"Ambainis","year":"2004","journal-title":"Parsimony hierarchies for inductive inference"},{"key":"S0022481200003534_ref033","volume-title":"Systems that Learn: An Introduction to Learning Theory for Cognitive and Computer Scientists","author":"Osherson","year":"1986"},{"key":"S0022481200003534_ref021","first-page":"219","volume-title":"Proceedings of the 4th Symposium on Mathematical Foundations of Computer Science","volume":"32","author":"Freivalds","year":"1975"},{"key":"S0022481200003534_ref041","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0249-3"},{"key":"S0022481200003534_ref029","first-page":"150","volume":"3","author":"Kleene","year":"1938","journal-title":"On notation for ordinal numbers"},{"key":"S0022481200003534_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(80)90285-5"},{"key":"S0022481200003534_ref044","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023786"},{"key":"S0022481200003534_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0012761"},{"key":"S0022481200003534_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/BF02218664"},{"key":"S0022481200003534_ref005","first-page":"455","volume-title":"Proceedings of the 20th International Congress of Mathematicians","author":"Barzdi\u0146\u0161","year":"1974"},{"key":"S0022481200003534_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(75)90261-2"},{"key":"S0022481200003534_ref037","volume-title":"Recursive Functions","author":"Peter","year":"1967"},{"key":"S0022481200003534_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00056-9"},{"key":"S0022481200003534_ref009","first-page":"143","volume-title":"Proceedings of the Business and Industry Symposium and the Military, Government, and Aerospace Simulation Symposium","author":"Burgin","year":"2005"},{"key":"S0022481200003534_ref003","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19960420138"},{"key":"S0022481200003534_ref024","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"S0022481200003534_ref010","first-page":"203","volume-title":"Proceedings of the 20th Annual Conference on Learning Theory","volume":"4539","author":"Carlucci","year":"2007"},{"key":"S0022481200003534_ref011","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793249694"},{"key":"S0022481200003534_ref026","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6610.001.0001","volume-title":"Systems that Learn: An Introduction to Learning Theory","author":"Jain","year":"1999"},{"key":"S0022481200003534_ref012","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054192000097"},{"key":"S0022481200003534_ref014","volume-title":"Program size complexity of correction grammars","author":"Case","year":"2008"},{"key":"S0022481200003534_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90061-0"},{"key":"S0022481200003534_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)80086-7"},{"key":"S0022481200003534_ref038","doi-asserted-by":"publisher","DOI":"10.1016\/0010-0277(79)90001-5"},{"key":"S0022481200003534_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0090937"},{"key":"S0022481200003534_ref032","volume-title":"An Introduction to the General Theory of Algorithms","author":"Machtey","year":"1978"},{"key":"S0022481200003534_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/BF02219847"},{"key":"S0022481200003534_ref023","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1068"},{"key":"S0022481200003534_ref025","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft","year":"1979"},{"key":"S0022481200003534_ref027","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90047-7"},{"key":"S0022481200003534_ref028","first-page":"221","volume-title":"Theory of Algorithms and Programs","volume":"1","author":"Kinber","year":"1974"},{"key":"S0022481200003534_ref031","doi-asserted-by":"publisher","DOI":"10.2307\/2372632"},{"key":"S0022481200003534_ref035","doi-asserted-by":"publisher","DOI":"10.1016\/0010-0277(82)90005-1"},{"key":"S0022481200003534_ref036","doi-asserted-by":"publisher","DOI":"10.1016\/0010-0277(84)90040-4"},{"key":"S0022481200003534_ref040","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers","year":"1967"},{"key":"S0022481200003534_ref007","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S0022481200003534_ref042","doi-asserted-by":"publisher","DOI":"10.1007\/s001530050112"},{"key":"S0022481200003534_ref043","volume-title":"Proof Theory","author":"Takeuti","year":"1987"},{"key":"S0022481200003534_ref045","doi-asserted-by":"publisher","DOI":"10.1016\/0010-0277(82)90006-3"},{"key":"S0022481200003534_ref030","doi-asserted-by":"publisher","DOI":"10.2307\/2371894"},{"key":"S0022481200003534_ref022","first-page":"3","volume-title":"Proceedings of the 3rd Annual Workshop on Computational Learning Theory","author":"Freivalds","year":"1990"},{"key":"S0022481200003534_ref018","first-page":"23","article-title":"A hierarchy of sets I","volume":"7","author":"Ershov","year":"1968","journal-title":"Algebra and Logic"},{"key":"S0022481200003534_ref034","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)80025-9"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200003534","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T02:08:26Z","timestamp":1589854106000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200003534\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["S0022481200003534"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1243948324","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}