Learning correction grammars. (English) Zbl 1193.03067

Summary: We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of computably enumerable (c.e.) languages. Knowing a language may feature a representation of it in terms of two 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 correction grammars. Correction grammars capture the observable fact that people do correct their linguistic utterances during their usual linguistic activities.
We show that learning correction grammars for classes of c.e. languages in the TxtEx-model (i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in the TxtBc-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each \(n \geq 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 \(n+1\) corrections to those that make \(n\) corrections.
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 \(u\) a notation in Kleene’s general system \((O,<_o)\) of ordinal notations for constructive ordinals, we introduce the concept of a \(u\)-correction grammar, where \(u\) is used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: if \(u\) and \(v\) are notations for constructive ordinals such that \(u<_o v\), then there are classes of c.e. languages that can be TxtEx-learned by conjecturing \(v\)-correction grammars but not by conjecturing \(u\)-correction grammars.
Surprisingly, we show that – above “\(\omega \)-many” corrections – it is not possible to strengthen the hierarchy: TxtEx-learning \(u\)-correction grammars of classes of c.e. languages, where \(u\) is a notation in \(O\) for any ordinal, can be simulated by TxtBc-learning \(w\)-correction grammars, where \(w\) is any notation for the smallest infinite ordinal \(\omega \).


03D05 Automata and formal grammars in connection with logical questions
68Q32 Computational learning theory
91E40 Memory and learning in psychology
Full Text: DOI


[1] Proceedings of the Business and Industry Symposium and the Military, Government, and Aerospace Simulation Symposium pp 143– (2005)
[2] Theory of Recursive Functions and Effective Computability (1967) · Zbl 0183.01401
[3] DOI: 10.1017/CBO9781107325944.011
[4] DOI: 10.1145/321386.321395 · Zbl 0155.01503
[5] DOI: 10.1016/0010-0277(79)90001-5
[6] DOI: 10.1016/S0019-9958(75)90261-2 · Zbl 0375.02028
[7] Recursive Functions (1967)
[8] Proceedings of the 20th International Congress of Mathematicians pp 455– (1974)
[9] DOI: 10.1016/0010-0277(84)90040-4
[10] Machine learning of higher order programs 59 pp 486– (1994) · Zbl 0814.03034
[11] DOI: 10.1002/malq.19960420138 · Zbl 0863.03018
[12] DOI: 10.1016/0010-0277(82)90005-1
[13] DOI: 10.1016/S0019-9958(80)90285-5 · Zbl 0459.68051
[14] DOI: 10.1016/S0019-9958(82)80025-9 · Zbl 0505.68038
[15] Parsimony hierarchies for inductive inference 69 pp 287– (2004)
[16] Systems that Learn: An Introduction to Learning Theory for Cognitive and Computer Scientists (1986)
[17] An Introduction to the General Theory of Algorithms (1978)
[18] DOI: 10.2307/2372632 · Zbl 0067.25203
[19] DOI: 10.2307/2371894 · Zbl 0061.01003
[20] On notation for ordinal numbers 3 pp 150– (1938)
[21] Theory of Algorithms and Programs 1 pp 221– (1974)
[22] DOI: 10.1016/0304-3975(94)90047-7 · Zbl 0938.68805
[23] Systems that Learn: An Introduction to Learning Theory (1999)
[24] Introduction to Automata Theory, Languages and Computation (1979) · Zbl 0426.68001
[25] DOI: 10.1016/S0019-9958(67)91165-5 · Zbl 0259.68032
[26] DOI: 10.1006/inco.1993.1068 · Zbl 0794.68127
[27] Proceedings of the 3rd Annual Workshop on Computational Learning Theory pp 3– (1990)
[28] Proceedings of the 4th Symposium on Mathematical Foundations of Computer Science 32 pp 219– (1975)
[29] DOI: 10.1007/BF02219847 · Zbl 0233.02017
[30] DOI: 10.1007/BF02218664
[31] Algebra and Logic 7 pp 23– (1968)
[32] Logic Year 1979-1980 859 pp 32– (1981)
[33] DOI: 10.1016/S0019-9958(82)80086-7 · Zbl 0531.03024
[34] DOI: 10.1016/0304-3975(83)90061-0 · Zbl 0524.03025
[35] Formal Principles of Language Acquisition (1980)
[36] Program size complexity of correction grammars (2008)
[37] DOI: 10.1016/0010-0277(82)90006-3
[38] DOI: 10.1007/BFb0012761
[39] DOI: 10.1007/BFb0023786
[40] DOI: 10.1142/S0129054192000097 · Zbl 0772.68068
[41] Proof Theory (1987)
[42] DOI: 10.1137/S0097539793249694 · Zbl 0939.68099
[43] Archive for Mathematical Logic 18 pp 521– (1998)
[44] Proceedings of the 20th Annual Conference on Learning Theory 4539 pp 203– (2007)
[45] Subrecursive Programming Systems: Complexity & Succinctness (1994) · Zbl 0941.68602
[46] DOI: 10.1016/0168-0072(94)00056-9 · Zbl 0844.03031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.