Passive learning for history-deterministic co-Buchi automata

We give a passive learning algorithm for languages recognized by history-deterministic co-Buchi automata. The algorithm can learn every language in this class in the limit, works in polynomial time with respect to a given sample, and for every language in the class, there is a characteristic sample of size polynomial in the minimal size of an automaton for the language. This is the first algorithm of this kind for any class of omega-languages, except for safety languages, that does not impose some additional restrictions on the congruences of the language or on the shape of automata recognizing the languages.

Authors

• Igor Walukiewicz

Keywords

No keywords are indexed for this paper.