Active Automata Learning: From DFAs to Interface Programs and Beyond

Bernhard Steffen, Falk Howar, Malte Isberner
; Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:195-209, 2012.

Abstract

This paper reviews the development of active learning in the last decade under the perspective of treating of data, a major source of undecidability, and therefore a key problem to achieve practicality. Starting with the first case studies, in which data was completely disregarded, we revisit different steps towards dealing with data explicitly in active learning: We discuss Mealy Machines as a model for systems with (data) output, automated alphabet abstraction refinement as a two-dimensional extension of the partition-refinement based approach of active learning for inferring not only states but also optimal alphabet abstractions, and Register Mealy Machines, which can be regarded as programs restricted to data-independent data processing as it is typical for protocols or interface programs. We are convinced that this development has the potential to transform active automata learning into a technology of high practical importance.

Cite this Paper


BibTeX
@InProceedings{pmlr-v21-steffen12a, title = {Active Automata Learning: From DFAs to Interface Programs and Beyond}, author = {Bernhard Steffen and Falk Howar and Malte Isberner}, booktitle = {Proceedings of the Eleventh International Conference on Grammatical Inference}, pages = {195--209}, year = {2012}, editor = {Jeffrey Heinz and Colin Higuera and Tim Oates}, volume = {21}, series = {Proceedings of Machine Learning Research}, address = {University of Maryland, College Park, MD, USA}, month = {05--08 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v21/steffen12a/steffen12a.pdf}, url = {http://proceedings.mlr.press/v21/steffen12a.html}, abstract = {This paper reviews the development of active learning in the last decade under the perspective of treating of data, a major source of undecidability, and therefore a key problem to achieve practicality. Starting with the first case studies, in which data was completely disregarded, we revisit different steps towards dealing with data explicitly in active learning: We discuss Mealy Machines as a model for systems with (data) output, automated alphabet abstraction refinement as a two-dimensional extension of the partition-refinement based approach of active learning for inferring not only states but also optimal alphabet abstractions, and Register Mealy Machines, which can be regarded as programs restricted to data-independent data processing as it is typical for protocols or interface programs. We are convinced that this development has the potential to transform active automata learning into a technology of high practical importance.} }
Endnote
%0 Conference Paper %T Active Automata Learning: From DFAs to Interface Programs and Beyond %A Bernhard Steffen %A Falk Howar %A Malte Isberner %B Proceedings of the Eleventh International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2012 %E Jeffrey Heinz %E Colin Higuera %E Tim Oates %F pmlr-v21-steffen12a %I PMLR %J Proceedings of Machine Learning Research %P 195--209 %U http://proceedings.mlr.press %V 21 %W PMLR %X This paper reviews the development of active learning in the last decade under the perspective of treating of data, a major source of undecidability, and therefore a key problem to achieve practicality. Starting with the first case studies, in which data was completely disregarded, we revisit different steps towards dealing with data explicitly in active learning: We discuss Mealy Machines as a model for systems with (data) output, automated alphabet abstraction refinement as a two-dimensional extension of the partition-refinement based approach of active learning for inferring not only states but also optimal alphabet abstractions, and Register Mealy Machines, which can be regarded as programs restricted to data-independent data processing as it is typical for protocols or interface programs. We are convinced that this development has the potential to transform active automata learning into a technology of high practical importance.
RIS
TY - CPAPER TI - Active Automata Learning: From DFAs to Interface Programs and Beyond AU - Bernhard Steffen AU - Falk Howar AU - Malte Isberner BT - Proceedings of the Eleventh International Conference on Grammatical Inference PY - 2012/08/16 DA - 2012/08/16 ED - Jeffrey Heinz ED - Colin Higuera ED - Tim Oates ID - pmlr-v21-steffen12a PB - PMLR SP - 195 DP - PMLR EP - 209 L1 - http://proceedings.mlr.press/v21/steffen12a/steffen12a.pdf UR - http://proceedings.mlr.press/v21/steffen12a.html AB - This paper reviews the development of active learning in the last decade under the perspective of treating of data, a major source of undecidability, and therefore a key problem to achieve practicality. Starting with the first case studies, in which data was completely disregarded, we revisit different steps towards dealing with data explicitly in active learning: We discuss Mealy Machines as a model for systems with (data) output, automated alphabet abstraction refinement as a two-dimensional extension of the partition-refinement based approach of active learning for inferring not only states but also optimal alphabet abstractions, and Register Mealy Machines, which can be regarded as programs restricted to data-independent data processing as it is typical for protocols or interface programs. We are convinced that this development has the potential to transform active automata learning into a technology of high practical importance. ER -
APA
Steffen, B., Howar, F. & Isberner, M.. (2012). Active Automata Learning: From DFAs to Interface Programs and Beyond. Proceedings of the Eleventh International Conference on Grammatical Inference, in PMLR 21:195-209

Related Material