T.: Polynomial time algorithms for learning k-reversible languages and pattern languages with correction queries

Abstract. We investigate two of the language classes intensively studied by the algorithmic learning theory community in the context of learning with correction queries. More precisely, we show that any pattern lan-guage can be inferred in polynomial time in length of the pattern by ask-ing just a linear number of correction queries, and that k-reversible lan-guages are efficiently learnable within this setting. Note that although the class of all pattern languages is learnable with membership queries, this cannot be done in polynomial time. Moreover, the class of k-reversible languages is not learnable at all using membership queries only