Learning Residual Alternating Automata

Authors

  • 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

DOI:

https://doi.org/10.1609/aaai.v31i1.10891

Keywords:

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

Abstract

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.

Downloads

Published

2017-02-13

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