On the Learnability of Infinitary Regular Sets
Abstract
In 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 Σ*.
Cite
Text
Maler and Pnueli. "On the Learnability of Infinitary Regular Sets." Annual Conference on Computational Learning Theory, 1991. doi:10.1006/inco.1995.1070Markdown
[Maler and Pnueli. "On the Learnability of Infinitary Regular Sets." Annual Conference on Computational Learning Theory, 1991.](https://mlanthology.org/colt/1991/maler1991colt-learnability/) doi:10.1006/inco.1995.1070BibTeX
@inproceedings{maler1991colt-learnability,
title = {{On the Learnability of Infinitary Regular Sets}},
author = {Maler, Oded and Pnueli, Amir},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1991},
pages = {128-136},
doi = {10.1006/inco.1995.1070},
url = {https://mlanthology.org/colt/1991/maler1991colt-learnability/}
}