Finite Automata synthesis from Interactions

by Erwan Mahe, Boutheina Bannour, Christophe Gaston, Arnault Lapitre (Université Paris-Saclay, CEA, List, Palaiseau, France), Pascale Le Gall (Université Paris-Saclay, CentraleSupélec, Gif-sur-Yvette, France).

Interactions are graphical models representing communication flows between actors. Well-known interaction languages include UML Sequence Diagrams or Message Sequence Charts. Even though interactions allow for concise and intuitive specifications, their use remains limited in formal verification, partly because the subsets of formalized languages often lack expressiveness. As many verification methods, such as model-checking or runtime verification, are routinely available for finite automata, we propose a new approach to generate finite automata from an expressive interaction language with operators such as the concurrent region. Our approach leverages an operational semantics to compute derivatives of an interaction and assimilate them to states of a finite automata. In addition, we use term rewriting to merge states on-the-fly so as to obtain small automata without relying on costly a-posteriori minimization techniques.