Compositional Automata Learning of Synchronous Systems
Open Access
- 20 April 2023
- book chapter
- Published by Springer Nature
- p. 47-66
Abstract
Automata learning is a technique to infer an automaton model of a black-box system via queries to the system. In recent years it has found widespread use both in industry and academia, as it enables formal verification when no model is available or it is too complex to create one manually. In this paper we consider the problem of learning the individual components of a black-box synchronous system, assuming we can only query the whole system. We introduce a compositional learning approach in which several learners cooperate, each aiming to learn one of the components. Our experiments show that, in many cases, our approach requires significantly fewer queries than a widely-used non-compositional algorithm such as $$\mathtt {L^*}$$ .
Keywords
This publication has 29 references indexed in Scilit:
- The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning2014
- Learning Minimal Deterministic Automata from Inexperienced Teachers2012
- Exact DFA Identification Using SAT Solvers2010
- Z3: An Efficient SMT Solver2008
- Inferring Network Invariants Automatically2006
- Learning Finite-State Machines from Inexperienced Teachers2006
- Learning Assumptions for Compositional Verification2003
- Synthesizing Distributed Transition Systems from Global Specifications1999
- Learning regular sets from queries and counterexamplesInformation and Computation, 1987
- Linear automaton transformationsProceedings of the American Mathematical Society, 1958