Compositional Learning of Mealy Machines with Projections

26 Oct 2026
Rick Koenders and Joshua Moerman
ICGI

Abstract

We consider parallel composition in the context of active automata learning. The problem we solve is that automata learning typically learns a single nite state machine for a system, even when the system is composed of smaller subsystems. We assume a closed-box setting, where the compositional structure of the system is not known and has to be inferred during learning. We develop a new algorithm, CoALP, which, like L* or TTT, learns the system but simultaneously learns a decomposition of the system. Depending on the structure of the system, this reduces the number of queries drastically, as shown by an evaluation of the algorithm. The algorithm CoALP is generic in the sense that it can use any learning algorithm for the subsystems.