13:00
14:00

Active automata learning infers automaton models of systems from behavioral observations, a technique successfully applied to a wide range of domains. Compositional approaches for concurrent systems have recently emerged. This talk presents a new framework allowing to take a significant step beyond available results and develop a general technique for compositional learning of a synchronizing parallel system with an unknown decomposition. The approach automatically refines the global alphabet into component alphabets while learning the component models. It is based on the development of a theoretical treatment of distributions of alphabets, i.e., sets of possibly overlapping component alphabets. This allows to characterize counter-examples that reveal inconsistencies with global observations, and show how to systematically update the distribution to restore consistency. Based on this theory, a compositional learning algorithm implementing these ideas is presented, where learning counterexamples precisely correspond to distribution counterexamples under well-defined conditions.Finally, some experiments are presented, showing that in more than 630 subject systems, the implementation of this new algorithm delivers orders of magnitude improvements (up to five orders) in membership queries and in systems with significant concurrency, it also achieves better scalability in the number of equivalence queries.

Français
LaBRI, salle 178