Author name cluster

Matthias Lutter

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

I&C Journal 2022 Journal Article

Learning residual alternating automata

Sebastian Berndt
Maciej Liśkiewicz
Matthias Lutter
Rüdiger Reischuk

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 (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 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 finite automata (FA) types in more detail.

Details DOI

AAAI Conference 2017 Conference Paper

Learning Residual Alternating Automata

Sebastian Berndt
Maciej Li_kiewicz
Matthias Lutter
Rdiger Reischuk

Residuality plays an essential role for learning ﬁnite 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 efﬁcient 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 Details