Learning Regular Languages via Alternating Automata / 3308
Dana Angluin, Sarah Eisenstat, Dana Fisman
PDF

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*.