On the Learnability of Infinitary Regular Sets

AbstractIn this paper we extend the automaton synthesis paradigm to infinitary languages, that is, to subsets of the set Σω of all infinite sequences over some alphabet Σ. Our main result is a polynomial algorithm for learning a sub-class of the ω-regular sets from membership queries and counter-examples based on the framework suggested by Angluin (Angluin, D. (1987), Inform. and Comput.75, 87-106) for learning regular subsets of Σ*