Learning Moore machines from input-output traces

Georgios Giantamidis*, Stavros Tripakis, Stylianos Basagiannis

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

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 compare the algorithms experimentally in terms of the size of the learned machine and several notions of accuracy, introduced in this paper. We also carry out a performance comparison against two existing tools (LearnLib and flexfringe). 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
Number of pages29
JournalInternational Journal on Software Tools for Technology Transfer
DOIs
Publication statusE-pub ahead of print - 6 Nov 2019
MoE publication typeA1 Journal article-refereed

Keywords

  • Finite state machine
  • Moore machine
  • Mealy machine
  • Automata learning
  • Passive learning
  • Characteristic sample
  • FINITE-STATE MACHINES
  • IDENTIFICATION
  • INFERENCE
  • GENERATION
  • AUTOMATA
  • SAMPLES

Cite this