Learning Residual Alternating Automata

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.

Original languageEnglish
Title of host publicationProc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017)
EditorsSatinder Singh
Number of pages26
Publisher AAAI Press
Publication date08.03.2017
Pages1749-1755
ISBN (Print)9781577357858
DOIs
Publication statusPublished - 08.03.2017
EventThirty-First AAAI Conference on Artificial Intelligence
- San Francisco, United States
Duration: 04.02.201709.02.2017
https://aaai.org/Conferences/AAAI/aaai17.php

Fingerprint

Dive into the research topics of 'Learning Residual Alternating Automata'. Together they form a unique fingerprint.

Cite this