TY - GEN
T1 - Automata learning with on-the-fly direct hypothesis construction
AU - Merten, Maik
AU - Howar, Falk
AU - Steffen, Bernhard
AU - Margaria, Tiziana
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84868368497&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-34781-8_19
DO - 10.1007/978-3-642-34781-8_19
M3 - Conference contribution
AN - SCOPUS:84868368497
SN - 9783642347801
T3 - Communications in Computer and Information Science
SP - 248
EP - 260
BT - Leveraging Applications of Formal Methods, Verification, and Validation - International Workshops, SARS 2011 and MLSC 2011, Held Under the Auspices of ISoLA 2011, Revised Selected Papers
T2 - International 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
Y2 - 17 October 2011 through 18 October 2011
ER -