Automata learning with on-the-fly direct hypothesis construction

Maik Merten, Falk Howar, Bernhard Steffen, Tiziana Margaria

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We present an active automata learning algorithm for Mealy state machines that directly constructs a state machine hypothesis according to observations, while other algorithms generate a state machine as output from information gathered in an observation table. Our DHC algorithm starts with a one-state hypothesis that it successively extends using a direct construction approach. This approach enables direct observation of the automata construction process: the learning algorithm continues to complete its hypothesis, providing intuition to a field of formal methods otherwise dominated by algorithms that largely operate on internal data structures without visible feedback. The DHC algorithm is competitive in cases where memory is the critical issue, e.g., in embedded networked systems. It is also well-suited as educational tool to teach the underlying well-established theoretical methods in a totally unbiased fashion, without cluttering the view onto the actual idea of the learning process with aspects only relevant to internal bookkeeping.

Original languageEnglish
Title of host publicationLeveraging Applications of Formal Methods, Verification, and Validation - International Workshops, SARS 2011 and MLSC 2011, Held Under the Auspices of ISoLA 2011, Revised Selected Papers
Pages248-260
Number of pages13
DOIs
Publication statusPublished - 2012
Externally publishedYes
EventInternational Workshops on Software Aspects of Robotic Systems, SARS 2011 and Machine Learning for System Construction, MLSC 2011, Held Under the Auspices of the ISoLA 2011 - Vienna, Austria
Duration: 17 Oct 201118 Oct 2011

Publication series

NameCommunications in Computer and Information Science
Volume336 CCIS
ISSN (Print)1865-0929

Conference

ConferenceInternational Workshops on Software Aspects of Robotic Systems, SARS 2011 and Machine Learning for System Construction, MLSC 2011, Held Under the Auspices of the ISoLA 2011
Country/TerritoryAustria
CityVienna
Period17/10/1118/10/11

Fingerprint

Dive into the research topics of 'Automata learning with on-the-fly direct hypothesis construction'. Together they form a unique fingerprint.

Cite this