Learning Residual Alternating Automata

Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk

AAAI 2017 pp. 1749-1755

doi:10.1609/AAAI.V31I1.10891 /aaai/2017/berndt2017aaai-learning/

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.

PDF AAAI Semantic Scholar

Cite

Text

Berndt et al. "Learning Residual Alternating Automata." AAAI Conference on Artificial Intelligence, 2017. doi:10.1609/AAAI.V31I1.10891

Markdown

[Berndt et al. "Learning Residual Alternating Automata." AAAI Conference on Artificial Intelligence, 2017.](https://mlanthology.org/aaai/2017/berndt2017aaai-learning/) doi:10.1609/AAAI.V31I1.10891

BibTeX

@inproceedings{berndt2017aaai-learning,
  title     = {{Learning Residual Alternating Automata}},
  author    = {Berndt, Sebastian and Liskiewicz, Maciej and Lutter, Matthias and Reischuk, Rüdiger},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2017},
  pages     = {1749-1755},
  doi       = {10.1609/AAAI.V31I1.10891},
  url       = {https://mlanthology.org/aaai/2017/berndt2017aaai-learning/}
}