Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/41134
DC FieldValue
dc.titleLearning correction grammars
dc.contributor.authorCarlucci, L.
dc.contributor.authorCase, J.
dc.contributor.authorJain, S.
dc.date.accessioned2013-07-04T08:20:24Z
dc.date.available2013-07-04T08:20:24Z
dc.date.issued2007
dc.identifier.citationCarlucci, L.,Case, J.,Jain, S. (2007). Learning correction grammars. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4539 LNAI : 203-217. ScholarBank@NUS Repository.
dc.identifier.isbn9783540729259
dc.identifier.issn03029743
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/41134
dc.description.abstractWe investigate a new paradigm in the context of learning in the limit: learning correction grammars for classes of r.e. languages. Knowing a language may feature a representation of the target language in terms of two sets of rules (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 r.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 > 0, there is a similar learning advantage, 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 trans-finite constructive ordinals. For u a notation in Kleene's general system (O, < o) of ordinal notations, we introduce the concept of an 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 r.e. languages that can be TxtEx-learned by conjecturing v-correction grammars but not by conjecturing u-correction grammars. Surprisingly, we show that -above "ω-many" corrections -it is not possible to strengthen the hierarchy: TxtEx-learning u-correction grammars of classes of r.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 ω. © Springer-Verlag Berlin Heidelberg 2007.
dc.sourceScopus
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.description.volume4539 LNAI
dc.description.page203-217
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Page view(s)

81
checked on Oct 6, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.