Active Automata Learning: From DFAs to Interface Programs and Beyond

Bernhard Steffen, Falk Howar, Malte Isberner: Active Automata Learning: From DFAs to Interface Programs and Beyond. In: ICGI 2012, JMLR W&CP Vol. 21, pp. 195-209. JMLR, 2012.


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.

Download PDF
Comments are closed for this post.