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.
|Title of host publication
|Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017)
|Number of pages
|Published - 08.03.2017
|Thirty-First AAAI Conference on Artificial Intelligence
- San Francisco, United States
Duration: 04.02.2017 → 09.02.2017