Learning Residual Alternating Automata

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

doi:https://aaai.org/ocs/index.php/AAAI/AAAI17/index

Learning Residual Alternating Automata

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

Institute of Theoretical Computer Science

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 language	English
Title of host publication	Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017)
Editors	Satinder Singh
Number of pages	26
Publisher	AAAI Press
Publication date	08.03.2017
Pages	1749-1755
ISBN (Print)	9781577357858
DOIs	https://doi.org/https://aaai.org/ocs/index.php/AAAI/AAAI17/index
Publication status	Published - 08.03.2017
Event	Thirty-First AAAI Conference on Artificial Intelligence - San Francisco, United States Duration: 04.02.2017 → 09.02.2017 https://aaai.org/Conferences/AAAI/aaai17.php

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

https://aaai.org/ocs/index.php/AAAI/AAAI17/index

https://eccc.weizmann.ac.il/report/2017/046/download

Cite this

@inproceedings{43e0450bb6e940038f10a628177e5bc8,

title = "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.",

author = "Sebastian Berndt and Maciej Liskiewicz and Matthias Lutter and R{\"u}diger Reischuk",

year = "2017",

month = mar,

day = "8",

doi = "https://aaai.org/ocs/index.php/AAAI/AAAI17/index",

language = "English",

isbn = "9781577357858",

series = "Electronic Colloquium on Computational Complexity (ECCC)",

publisher = " AAAI Press",

pages = "1749--1755",

editor = "Singh, {Satinder }",

booktitle = "Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017)",

note = "Thirty-First AAAI Conference on Artificial Intelligence<br/> ; Conference date: 04-02-2017 Through 09-02-2017",

url = "https://aaai.org/Conferences/AAAI/aaai17.php",

}

Berndt, S , Liskiewicz, M, Lutter, M & Reischuk, R 2017, Learning Residual Alternating Automata. in S Singh (ed.), Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017). Electronic Colloquium on Computational Complexity (ECCC), AAAI Press, pp. 1749-1755, Thirty-First AAAI Conference on Artificial Intelligence
, San Francisco, California, United States, 04.02.17. https://doi.org/https://aaai.org/ocs/index.php/AAAI/AAAI17/index

Learning Residual Alternating Automata. / Berndt, Sebastian ; Liskiewicz, Maciej; Lutter, Matthias et al.
Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017). ed. / Satinder Singh. AAAI Press, 2017. p. 1749-1755 (Electronic Colloquium on Computational Complexity (ECCC)).

Research output: Chapters in Books/Reports/Conference Proceedings › Conference contribution › peer-review

TY - GEN

T1 - Learning Residual Alternating Automata

AU - Berndt, Sebastian

AU - Liskiewicz, Maciej

AU - Lutter, Matthias

AU - Reischuk, Rüdiger

PY - 2017/3/8

Y1 - 2017/3/8

N2 - 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.

AB - 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.

UR - https://eccc.weizmann.ac.il/report/2017/046/

U2 - https://aaai.org/ocs/index.php/AAAI/AAAI17/index

DO - https://aaai.org/ocs/index.php/AAAI/AAAI17/index

M3 - Conference contribution

SN - 9781577357858

T3 - Electronic Colloquium on Computational Complexity (ECCC)

SP - 1749

EP - 1755

BT - Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017)

A2 - Singh, Satinder

PB - AAAI Press

T2 - Thirty-First AAAI Conference on Artificial Intelligence<br/>

Y2 - 4 February 2017 through 9 February 2017

ER -

Learning Residual Alternating Automata

Abstract

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this