Equivalence of denotational and operational semantics for interaction languages

Erwan Mahe (1) , Christophe Gaston (1) , Pascale Le Gall (2)

1 LECS - Laboratoire Exigences et Conformité des Systèmes
2 CentraleSupélec

Message Sequence Charts (MSC) and Sequence Diagrams (SD) are graphical models that represent the behaviours of distributed and concurrent systems via the scheduling of discrete emission and reception events. In order to exploit them as support for formal methods, a mathematical semantics is required. In the literature, two kinds of semantics are classically proposed: denotational semantics, well suited to reason about algebraic properties and operational semantics, well suited to be the basis of verification algorithms. We define an algebraic language to specify so-called interactions, similar to the MSC and SD models. This language is equipped with a denotational semantics associating a set of traces (sequences of observed events) to each interaction. We then define a structural operational semantics in the style of process algebras and formally prove the equivalence of the two semantics.

Domaines: Théorie et langage formel [cs.FL]

Erwan Mahe, Christophe Gaston, Pascale Le Gall. Equivalence of denotational and operational semantics for interaction languages. Lecture Notes in Computer Science, 2022, Theoretical Aspects of Software Engineering, 13299, pp.113-130. ⟨10.1007/978-3-031-10363-6_8⟩. ⟨cea-04060492⟩