Learning Regular Languages via Alternating Automata
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Machine Learning. Pages 3308-3313.
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*.
@inproceedings{ijcai2015p466,
title = {Learning Regular Languages via Alternating Automata},
author = {Angluin, Dana and Eisenstat, Sarah and Fisman, Dana},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {3308--3313},
year = {2015},
month = {7},
note = {Special Track on Machine Learning},
url = {https://ijcai.org/proceedings/2015/466},
}
TY - CPAPER TI - Learning Regular Languages via Alternating Automata AU - Angluin, Dana AU - Eisenstat, Sarah AU - Fisman, Dana T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 3308 EP - 3313 UR - https://ijcai.org/proceedings/2015/466 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
