Learning Abstracted Non-deterministic Finite State Machines

Andrea Pferscher*, Bernhard Aichernig

*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in Buch/Bericht/KonferenzbandBeitrag in einem KonferenzbandBegutachtung


Active automata learning gains increasing interest since it gives an insight into the behavior of a black-box system. A crucial drawback of the frequently used learning algorithms based on Angluin’s L is that they become impractical if systems with a large input/output alphabet are learned. Previous work suggested to circumvent this problem by abstracting the input alphabet and the observed outputs. However, abstraction could introduce non-deterministic behavior. Already existing active automata learning algorithms for observable non-deterministic systems learn larger models if outputs are only observable after certain input/output sequences. In this paper, we introduce an abstraction scheme that merges akin states. Hence, we learn a more generic behavioral model of a black-box system. Furthermore, we evaluate our algorithm in a practical case study. In this case study, we learn the behavior of five different Message Queuing Telemetry Transport (mqtt) brokers interacting with multiple clients.

TitelTesting Software and Systems - 32nd IFIP WG 6.1 International Conference, ICTSS 2020, Proceedings
Untertitel32nd IFIP WG 6.1 International Conference, ICTSS 2020, Naples, Italy, December 9-11, 2020, Proceedings
Redakteure/-innenValentina Casola, Alessandra De Benedictis, Massimiliano Rak
Herausgeber (Verlag)Springer
ISBN (Print)978-3-030-64880-0
PublikationsstatusVeröffentlicht - Dez. 2020
Veranstaltung32nd IFIP International Conference on Testing Software and Systems: ICTSS 2020 - Virtuell, Italien
Dauer: 9 Dez. 202011 Dez. 2020


NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band12543 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349


Konferenz32nd IFIP International Conference on Testing Software and Systems
KurztitelIFIP-ICTSS 2020

ASJC Scopus subject areas

  • Theoretische Informatik
  • Informatik (insg.)

Fields of Expertise

  • Information, Communication & Computing

Dieses zitieren