Resumen de Language learning with correction queries
In the field of grammatical inference, the goal of any learning algorithm is to identify a target concept from a given class by having access to a specific type of information. The main learning settings are Gold's model of learning in the limit and Angluin's query learning. This dissertation is primarily concerned with the second approach.We thoroughly investigate a recently introduced, linguistic motivated, type of query called Correction Query (CQ). We consider three possible definitions, and for each of them we give necessary and sufficient conditions for a language class to be learnable with these types of queries. Furthermore, we compare the model of learning with CQs with other well-known Gold-style and query learning models when no efficiency constraints are imposed. Results are also obtained for the restricted version of the model of learning with CQs in polynomial time. Additionally, we discuss the learnability of deterministic finite automata (DFAs) with correction and equivalence queries. We design several learning algorithms and we present a comparison between our algorithms and the standard algorithm for learning DFAs with membership and equivalence queries. These results are furthermore extended from string languages to tree languages.
