Learning Moore Machines from Input-Output Traces

Georgios Giantamidis, Stavros Tripakis

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

17 Citations (Scopus)

Abstract

The problem of learning automata from example traces (but no equivalence or membership queries) is fundamental in automata learning theory and practice. In this paper we study this problem for finite state machines with inputs and outputs, and in particular for Moore machines. We develop three algorithms for solving this problem: (1) the PTAP algorithm, which transforms a set of input-output traces into an incomplete Moore machine and then completes the machine with self-loops; (2) the PRPNI algorithm, which uses the well-known RPNI algorithm for automata learning to learn a product of automata encoding a Moore machine; and (3) the MooreMI algorithm, which directly learns a Moore machine using PTAP extended with state merging. We prove that MooreMI has the fundamental identification in the limit property. We also compare the algorithms experimentally in terms of the size of the learned machine and several notions of accuracy, introduced in this paper. Finally, we compare with OSTIA, an algorithm that learns a more general class of transducers, and find that OSTIA generally does not learn a Moore machine, even when fed with a characteristic sample.
Original languageEnglish
Title of host publicationFM 2016: Formal Methods
EditorsJohn Fitzgerald, Constance Heitmeyer, Stefania Gnesi, Anna Philippou
Pages291-309
ISBN (Electronic)978-3-319-48989-6
DOIs
Publication statusPublished - 8 Nov 2016
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Formal Methods - Limassol, Cyprus
Duration: 9 Nov 201611 Nov 2016
Conference number: 21

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9995
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Symposium on Formal Methods
Abbreviated titleFM
CountryCyprus
CityLimassol
Period09/11/201611/11/2016

Fingerprint Dive into the research topics of 'Learning Moore Machines from Input-Output Traces'. Together they form a unique fingerprint.

Cite this