Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries

摘要

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 language can be inferred in polynomial time in length of the pattern by asking just a linear number of correction queries, and that fc-reversible languages 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 fc-reversible languages is not learnable at all using membership queries only.