文章基本信息

标题：Learning Residual Alternating Automata
本地全文：下载
作者：Sebastian Berndt ; Maciej Li\'skiewicz ; Matthias Lutter 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2017
卷号：2017
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Residuality plays an essential role for learning finite automata. While residual deterministic and nondeterministic automata have been understood quite well, fundamental questions concerning alternating automata (AFA) remain open. Recently, Angluin, Eisenstat, and Fisman 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 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.
关键词：alternating automata ; learning algorithms ; residual automata ; succinctness