Learning correction grammars
Lorenzo Carlucci, John Case, Sanjay K. Jain · Journal of Symbolic Logic · 2009
Abstract We investigate a new paradigm in the context of learning in the limit, namely, learningcorrection grammarsfor classes ofcomputably enumerable (c.e.)languages. Knowing a language may feature a representation of it in terms oftwogrammars. 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 grammarscorrection grammars. Correction grammars capture the observable fact that peopledocorrect their linguistic utterances during their usual linguistic activities. We show that learning correction grammars for classes of c.e. languages in theTxtEx-mode(i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in theTxtBc-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For eachn≥ 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 maken+ 1 corrections to those that makencorrections. 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. Forua notation in Kleene's general system (O, <o) of ordinal notations for constructive ordinals, we introduce the concept of anu-correction grammar, whereuis used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: ifuandvare notations for constructive ordinals such thatu