T̂ırnăucă, C.: Learning DFA from correction and equivalence queries

Abstract. In active learning, membership queries and equivalence que-ries have established themselves as the standard combination to be used. However, they are quite “unnatural ” for real learning environments (mem-bership queries are oversimplified and equivalence queries do not have a correspondence in a real life setting). Based on several linguistic argu-ments that support the presence of corrections in children’s language acquisition, we propose another kind of query called correction query. We provide an algorithm that learns DFA using correction and equiv-alence queries in polynomial time. Despite the fact that the worst case complexity of our algorithm is not better than Angluin’s algorithm, we show through a large number of experiments that the average number of queries is considerably reduced by using correction queries