Learning Residual Alternating Automata


  • Sebastian Berndt University of Lübeck
  • Maciej Liśkiewicz University of Lübeck
  • Matthias Lutter University of Lübeck
  • Rüdiger Reischuk University of Lübeck




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


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.




How to Cite

Berndt, S., Liśkiewicz, M., Lutter, M., & Reischuk, R. (2017). Learning Residual Alternating Automata. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10891