An incremental learning algorithm for extended mealy automata
2012 (English)In: Leveraging Applications of Formal Methods, Verification and Validation. Technologies for Mastering Change: 5th International Symposium, ISoLA 2012, Heraklion, Crete, Greece, October 15-18, 2012, Proceedings, Part I / [ed] Tiziana Margaria, Bernhard Steffen, Springer, 2012, no PART 1, 488-504 p.Conference paper (Refereed)
We present a new algorithm ICGE for incremental learning of extended Mealy automata computing over abstract data types. Our approach extends and refines our previous research on congruence generator extension (CGE) as an algebraic approach to automaton learning. In the congruence generator approach, confluent terminating string rewriting systems (SRS) are used to represent hypothesis automata. We show how an approximating sequence R 0 , R 1 , ... of confluent terminating SRS can be directly and incrementally generated from observations about the loop structure of an unknown automaton A. Such an approximating sequence converges finitely if A is finite state, and converges in the limit if A is an infinite state automaton.
Place, publisher, year, edition, pages
Springer, 2012. no PART 1, 488-504 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 7609 LNCS
algebraic automata theory, computational learning theory, finite state machine, initial algebra, Mealy automaton, string rewriting
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-107321DOI: 10.1007/978-3-642-34026-0_36ScopusID: 2-s2.0-84868298586ISBN: 978-364234025-3OAI: oai:DiVA.org:kth-107321DiVA: diva2:576036
5th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation: Technologies for Mastering Change, ISoLA 2012, 15 October 2012 through 18 October 2012, Heraklion, Crete
QC 201212122012-12-122012-12-102012-12-12Bibliographically approved