Learning Regular Omega Languages
Abstract
We provide an algorithm for learning an unknown regular set of infinite words, using membership and equivalence queries. Three variations of the algorithm learn three different canonical representations of omega regular languages, using the notion of families of dfa s. One is of size similar to L _$, a dfa representation recently learned using L * [7]. The second is based on the syntactic forc , introduced in [14]. The third is introduced herein. We show that the second can be exponentially smaller than the first, and the third is at most as large as the first two, with up to a quadratic saving with respect to the second.
Cite
Text
Angluin and Fisman. "Learning Regular Omega Languages." International Conference on Algorithmic Learning Theory, 2014. doi:10.1007/978-3-319-11662-4_10Markdown
[Angluin and Fisman. "Learning Regular Omega Languages." International Conference on Algorithmic Learning Theory, 2014.](https://mlanthology.org/alt/2014/angluin2014alt-learning/) doi:10.1007/978-3-319-11662-4_10BibTeX
@inproceedings{angluin2014alt-learning,
title = {{Learning Regular Omega Languages}},
author = {Angluin, Dana and Fisman, Dana},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2014},
pages = {125-139},
doi = {10.1007/978-3-319-11662-4_10},
url = {https://mlanthology.org/alt/2014/angluin2014alt-learning/}
}