Learning Communicating State Machines

We consider the problems of learning and conformance testing of components in a modular system. We assume that each component can be modelled as a Finite State Machine (FSM), the topology of the system is known, but some (or all) component FSMs are unknown and have to be learned by testing the whole system, as it cannot be disassembled. Thus the classical problem of active inference of an automaton in isolation is now further lifted to a system of communicating FSMs of an arbitrary topology. As opposed to the existing work on automata learning, the proposed approach neither needs a Minimally Adequate Teacher, also called the Oracle, nor uses it a conformance tester to approximate equivalence queries. The approach further enhances a SAT solving method suggested by the authors and allows to adaptively test conformance of a system with unknown components assuming that internal communications are observable. The resulting tests are much smaller than the classical universal conformance tests derived from the composite machine of the system.