Learning Minimal Deterministic Automata from Inexperienced Teachers

Martin Leucker; Daniel Neider

doi:10.1007/978-3-642-34026-0_39

Learning Minimal Deterministic Automata from Inexperienced Teachers

Institute of Software Engineering and Programming Languages

Abstract

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 language	English
Title of host publication	Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change
Editors	Tiziana Margaria, Bernhard Steffen
Number of pages	15
Volume	7609 LNCS
Place of Publication	Berlin
Publisher	Springer Verlag
Publication date	07.11.2012
Edition	PART 1
Pages	524-538
ISBN (Print)	978-3-642-34025-3
ISBN (Electronic)	978-3-642-34026-0
DOIs	https://doi.org/10.1007/978-3-642-34026-0_39
Publication status	Published - 07.11.2012
Event	5th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation: Technologies for Mastering Change - Heraklion, Crete, Greece Duration: 15.10.2012 → 18.10.2012 Conference number: 93454

UN SDGs

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

Access to Document

10.1007/978-3-642-34026-0_39

Cite this

Leucker, M., & Neider, D. (2012). Learning Minimal Deterministic Automata from Inexperienced Teachers. In T. Margaria, & B. Steffen (Eds.), Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change (PART 1 ed., Vol. 7609 LNCS, pp. 524-538). (Lecture Notes in Computer Science; Vol. 7609 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-34026-0_39

@inproceedings{519b5b707b294523a115092a0098a805,

title = "Learning Minimal Deterministic Automata from Inexperienced Teachers",

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

author = "Martin Leucker and Daniel Neider",

year = "2012",

month = nov,

day = "7",

doi = "10.1007/978-3-642-34026-0_39",

language = "English",

isbn = "978-3-642-34025-3",

volume = "7609 LNCS",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "524--538",

editor = "Margaria, { Tiziana} and Bernhard Steffen",

booktitle = "Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change",

edition = "PART 1",

note = "5th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation: Technologies for Mastering Change <br/>, ISoLA 2012 ; Conference date: 15-10-2012 Through 18-10-2012",

}

Leucker, M & Neider, D 2012, Learning Minimal Deterministic Automata from Inexperienced Teachers. in T Margaria & B Steffen (eds), Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change . PART 1 edn, vol. 7609 LNCS, Lecture Notes in Computer Science, vol. 7609 LNCS, Springer Verlag, Berlin, pp. 524-538, 5th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation: Technologies for Mastering Change
, Crete, Greece, 15.10.12. https://doi.org/10.1007/978-3-642-34026-0_39

Learning Minimal Deterministic Automata from Inexperienced Teachers. / Leucker, Martin; Neider, Daniel.
Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change . ed. / Tiziana Margaria; Bernhard Steffen. Vol. 7609 LNCS PART 1. ed. Berlin: Springer Verlag, 2012. p. 524-538 (Lecture Notes in Computer Science; Vol. 7609 LNCS).

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

TY - GEN

T1 - Learning Minimal Deterministic Automata from Inexperienced Teachers

AU - Leucker, Martin

AU - Neider, Daniel

N1 - Conference code: 93454

PY - 2012/11/7

Y1 - 2012/11/7

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

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

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-84868285316&origin=inward&txGid=748d42113d8dfe7f8eb0b55a865df2de

U2 - 10.1007/978-3-642-34026-0_39

DO - 10.1007/978-3-642-34026-0_39

M3 - Conference contribution

SN - 978-3-642-34025-3

VL - 7609 LNCS

T3 - Lecture Notes in Computer Science

SP - 524

EP - 538

BT - Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change

A2 - Margaria, Tiziana

A2 - Steffen, Bernhard

PB - Springer Verlag

CY - Berlin

T2 - 5th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation: Technologies for Mastering Change <br/>

Y2 - 15 October 2012 through 18 October 2012

ER -

Leucker M, Neider D. Learning Minimal Deterministic Automata from Inexperienced Teachers. In Margaria T, Steffen B, editors, Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change . PART 1 ed. Vol. 7609 LNCS. Berlin: Springer Verlag. 2012. p. 524-538. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-34026-0_39

Learning Minimal Deterministic Automata from Inexperienced Teachers

Abstract

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this