Learning Minimal Deterministic Automata from Inexperienced Teachers

Martin Leucker, Daniel Neider


A prominent learning algorithm is Angluin's L* algorithm, which allows to learn a minimal deterministic automaton using so-called membership and equivalence queries addressed to a teacher. In many applications, however, a teacher might be unable to answer some of the membership queries because parts of the object to learn are not completely specified, not observable, it is too expensive to resolve these queries, etc. Then, these queries may be answered inconclusively. In this paper, we survey different algorithms to learn minimal deterministic automata in this setting in a coherent fashion. Moreover, we provide modifications and improvements for these algorithms, which are enabled by recent developments.

Original languageEnglish
Title of host publication Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change
Editors Tiziana Margaria, Bernhard Steffen
Number of pages15
Volume7609 LNCS
Place of PublicationBerlin
PublisherSpringer Verlag
Publication date07.11.2012
EditionPART 1
ISBN (Print)978-3-642-34025-3
ISBN (Electronic)978-3-642-34026-0
Publication statusPublished - 07.11.2012
Event5th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation: Technologies for Mastering Change
- Heraklion, Crete, Greece
Duration: 15.10.201218.10.2012
Conference number: 93454


Dive into the research topics of 'Learning Minimal Deterministic Automata from Inexperienced Teachers'. Together they form a unique fingerprint.

Cite this