Learning infinite-word automata with loop-index queries

摘要

We propose a new framework for active learning of deterministic infinite-words automata. In our framework, the teacher answers standard membership and equivalence queries, and additionally it provides the loop index of the target automaton on wvω, which is the minimal number of letters of wvω past which the target automaton reaches the final cycle on wvω. We argue that in potential applications if one can answer Boolean part in membership (and equivalence) queries, one can compute the loop index as well.