AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Learning Residual Alternating Automata
Sebastian Berndt, Maciej Liśkiewicz, Matthias Lutter, Rüdiger Reischuk

Last modified: 2017-02-13


Residuality plays an essential role for learning finite automata. While residual deterministic and non-deterministic automata have been understood quite well, fundamental questions concerning alternating automata (AFA) remain open. Recently, Angluin, Eisenstat, and Fisman (2015) have initiated a systematic study of residual AFAs and proposed an algorithm called AL* – an extension of the popular L* algorithm – to learn AFAs. Based on computer experiments they have conjectured that AL* produces residual AFAs, but have not been able to give a proof. In this paper we disprove this conjecture by constructing a counterexample. As our main positive result we design an efficient learning algorithm, named AL** and give a proof that it outputs residual AFAs only. In addition, we investigate the succinctness of these different FA types in more detail.


learning finite automata; active learning; exact learning; alternating finite automata; membership and equivalence queries

Full Text: PDF