ML Anthology

Learning Regular Languages via Alternating Automata

Dana Angluin, Sarah Eisenstat, Dana Fisman
IJCAI 2015 pp. 3308-3314
/ijcai/2015/angluin2015ijcai-learning/

Abstract

Nearly all algorithms for learning an unknown regular language, in particular the popular L* algorithm, yield deterministic finite automata. It was recently shown that the ideas of L* can be extended to yield non-deterministic automata, and that the respective learning algorithm, NL*, outperforms L* on randomly generated regular expressions. We conjectured that this is due to the existential nature of regular expressions, and NL* might not outperform L* on languages with a universal nature. In this paper we introduce UL* — a learning algorithm for universal automata (the dual of non-deterministic automata); and AL* — a learning algorithm for alternating automata (which generalize both universal and non-deterministic automata). Our empirical results illustrate the advantages and trade-offs among L*, NL*, UL* and AL*.

PDF IJCAI Semantic Scholar

Cite

Text

Angluin et al. "Learning Regular Languages via Alternating Automata." International Joint Conference on Artificial Intelligence, 2015.

Markdown

[Angluin et al. "Learning Regular Languages via Alternating Automata." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/angluin2015ijcai-learning/)

BibTeX

@inproceedings{angluin2015ijcai-learning,
  title     = {{Learning Regular Languages via Alternating Automata}},
  author    = {Angluin, Dana and Eisenstat, Sarah and Fisman, Dana},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2015},
  pages     = {3308-3314},
  url       = {https://mlanthology.org/ijcai/2015/angluin2015ijcai-learning/}
}