Laboratoire de Mathématiques et Informatique pour la Complexité et les Systèmes, CentraleSupélec, 9 rue Joliot-Curie, Gif-sur-Yvette, Francehttps://orcid.org/0000-0002-5322-4337 Laboratory of Systems Requirements and Conformity Engineering, CEA-LIST, P.C. 174, Gif-sur-Yvette, Francehttps://orcid.org/0000-0001-6865-5108 Laboratoire de Mathématiques et Informatique pour la Complexité et les Systèmes, CentraleSupélec, 9 rue Joliot-Curie, Gif-sur-Yvette, Francehttps://orcid.org/0000-0002-8955-6835 \CopyrightErwan Mahe and Chritophe Gaston and Pascale Le Gall {CCSXML} <ccs2012> <concept> <concept_id>10003752.10010124.10010131.10010133</concept_id> <concept_desc>Theory of computation Denotational semantics</concept_desc> <concept_significance>300</concept_significance> </concept> <concept> <concept_id>10003752.10010124.10010131.10010134</concept_id> <concept_desc>Theory of computation Operational semantics</concept_desc> <concept_significance>300</concept_significance> </concept> <concept> <concept_id>10003752.10003753.10003761.10003764</concept_id> <concept_desc>Theory of computation Process calculi</concept_desc> <concept_significance>300</concept_significance> </concept> </ccs2012> \ccsdesc[300]Theory of computation Denotational semantics \ccsdesc[300]Theory of computation Operational semantics \ccsdesc[300]Theory of computation Process calculi \hideLIPIcs\EventEditors \EventNoEds1 \EventLongTitle \EventShortTitle \EventAcronym \EventYear \EventDate \EventLocation \EventLogo \SeriesVolume \ArticleNo

A structural operational semantics for interactions with a look at loops

Erwan Mahe Christophe Gaston Pascale Le Gall

Abstract

Message Sequence Charts & Sequence Diagrams are graphical models that represent the behavior of distributed and concurrent systems via the scheduling of discrete and local emission and reception events. We propose an Interaction Language (IL) to formalize such models, defined as a term algebra which includes strict and weak sequencing, alternative and parallel composition and four kinds of loops. This IL is equipped with a denotational-style 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 both semantics.

keywords:

interactions, sequence diagrams, distributed & concurrent systems, formal language, denotational semantics, operational semantics, loop

category:

\relatedversion

1 Introduction

Specifying the behavior of distributed and concurrent systems is the object of a large literature. In particular modelling asynchronous communications between concurrent processes is possible under a variety of formalisms, including process algebras [18], Petri Nets [4], series-parallel languages [9], distributed automata [1], or formalisms derived from Message Sequence Charts (MSC) [14]. In the context of this paper, we focus on the latter. MSCs are graphical models which represent the exchange of information between sub-systems. Various offshoots of MSCs, which notably include UML Sequence Diagrams (UML-SD), have been proposed and we may call languages from that family "Interaction Languages" (IL). Interactions are particularly interesting due to their graphical nature and ease of understanding.

In order to use interactions for formal verification, they have to be fitted with formal semantics. A major hurdle in defining those lies in the treatment of weak sequencing. In a few words, weak sequencing allows events taking place on different locations to occur in any order while strictly ordering those that take place on the same location. The survey [15] provides an overview of solutions found in the literature. Those can be roughly categorized as follows: (a) direct denotational semantics, which define the trace semantics of interactions directly. They either rely on partial order sets [19, 13] or algebraic operators [7]; (b) semantics by translation, which rely on translating interactions into some other models such as Petri Nets [3] or automata [8] and then use (generally operational-style) semantics of those other formalisms and; (c) direct operational-style semantics, which notably include that of [14].

While approaches in (c) are highly valuable for defining algorithms for formal verification, approaches in (a) are adapted to reason about interactions and their properties. Our contribution provides a framework encompassing (a) and (c) based on an IL which includes strict and weak sequencing, alternative and parallel composition and four semantically distinct loops. We propose a denotational-style semantics extending that of [7] with the addition of repetition operators in the form of variants of the algebraic Kleene closure. We also define a structural operational semantics in the fashion of process algebras [2] with a particular care for the handling of weak sequencing and which uses dedicated rules to address the various loops. The equivalence of both semantics is formally proven (with an automated proof made with Coq available in [11]). Languages such as MSC or UML-SD only propose a single loop construct. By contrast, our contribution highlights the use of distinct loops to express nuances in the repetition of behaviors.

This paper is organized as follows: Sec.2 introduces the concept of interactions and traces. Sec.3 defines repetition operators on sets of traces. Sec.4 presents the syntax of our IL and defines a trace semantics in denotational-style using operators introduced in the previous sections. Sec.5 defines a structural operational semantics on interactions with loops in the style of process calculus. In Sec.6, we demonstrate the equivalence of both semantics. Finally, in Sec.7 we discuss some related works and we conclude in Sec.8. Detailed demonstrations are included in the appendix.

2 Basic interactions & intuition of their meaning

Interactions describe the behavior of distributed and concurrent systems through the perspective of their internal and external communications. They are defined up to a signature $\Omega=(L,M)$ where $L$ is a set of lifelines and $M$ is a set of messages. Lifelines are abstractions of sub-systems, or groups of sub-systems while messages represent data sent and received by sub-systems.

2.1 Preliminaries

The executions of systems are characterized by sequences of events called communication actions (actions for short) which are of two kinds: either the emission of a message $m\in M$ from a lifeline $l\in L$ , denoted by $l!m$ , or the reception of a message $m\in M$ by a lifeline $l\in L$ , denoted by $l?m$ . We note $\mathbb{A}_{\Omega}$ the set of actions defined up to $\Omega$ . For any such action $a$ , $\theta(a)$ denotes the lifeline on which $a$ occurs.

Sequences of actions from $\mathbb{A}_{\Omega}$ , called traces, are words in $\mathbb{A}_{\Omega}^{*}$ , with "." denoting the classical concatenation law and $\epsilon$ being the empty word (empty trace). We denote by $\mathbb{T}_{\Omega}=\mathbb{A}_{\Omega}^{*}$ the set of traces. Thus, for any two traces $t_{1}$ and $t_{2}$ , $t_{1}.t_{2}$ is the trace composed of the sequence of actions of $t_{1}$ followed by the sequence of actions of $t_{2}$ .

We now introduce operators¹¹1We use notations from [7]. to compose traces. Those operators model different notions of scheduling: the interleaving ( $||$ ) and the weak sequencing ( $;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ ).

The set $t_{1}||t_{2}$ of interleavings of traces $t_{1}$ and $t_{2}$ is defined by:

\begin{array}[]{lcl}\epsilon||t_{2}&=&\{t_{2}\}\\ t_{1}||\epsilon&=&\{t_{1}\}\\ (a_{1}.t_{1})||(a_{2}.t_{2})&=&\{a_{1}.t\leavevmode\nobreak\ |\leavevmode\nobreak\ t\in t_{1}||(a_{2}.t_{2})\}\cup\{a_{2}.t\leavevmode\nobreak\ |\leavevmode\nobreak\ t\in(a_{1}.t_{1})||t_{2}\}\end{array}

Interleaving allows elements of distinct traces to be reordered w.r.t. one another while preserving the order that is specific to each trace. By contrast, weak sequencing only allows such permutations when actions do not occur on the same lifeline. Defining weak sequencing requires introducing a predicate: for any trace $t$ and lifeline $l$ , the predicate $t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l$ means that $t$ contains at least an action occurring on $l$ (we say that $t$ has conflicts w.r.t. $l$ ). It is defined as follows:

\begin{array}[]{lcl}\epsilon\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l&=&\bot\\ (a.t)\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l&=&(\theta(a)=l)\vee(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)\end{array}

The set $t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2}$ of weak sequencing of traces $t_{1}$ and $t_{2}$ is defined by:

\begin{array}[]{lcl}\epsilon;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2}&=&\{t_{2}\}\\ t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\epsilon&=&\{t_{1}\}\\ (a_{1}.t_{1});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}(a_{2}.t_{2})&=&\{a_{1}.t\leavevmode\nobreak\ |\leavevmode\nobreak\ t\in t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}(a.t_{2})\}\cup\left\{a_{2}.t\leavevmode\nobreak\ \middle|\leavevmode\nobreak\ \begin{array}[]{c}t\in(a_{1}.t_{1});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2},\;\neg(a_{1}.t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a_{2}))\end{array}\right\}\end{array}

The previous binary operators (".", " $;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ " & " $||$ ") defined on traces are canonically extended to sets of traces as follows. Given $T_{1}$ and $T_{2}$ two sets of traces, $T_{1};T_{2}$ denotes the set of all traces $t_{1}.t_{2}$ s.t. $t_{1}\in T_{1}$ and $t_{2}\in T_{2}$ . Likewise, with $\diamond\in\{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}},\leavevmode\nobreak\ ||\}$ , $T_{1}\diamond T_{2}$ is the union of all the sets $t_{1}\diamond t_{2}$ s.t. $t_{1}\in T_{1}$ and $t_{2}\in T_{2}$ . By choosing ";" for denoting the extension of "." to sets of traces, we adopt the same notation as in [7]. ";" is called the strict sequencing operator. The use of the strict sequencing (";"), weak sequencing (" $;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ ") and interleaving (" $||$ ") operators is illustrated on the right of Fig.1 so as to compute the semantics of an example interaction. For instance, weak sequencing allows ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{1}!m_{2}}$ to be reordered before ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{3}?m_{1}}$ but not before ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}$ while interleaving allows ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}l_{1}!m_{4}}$ to be placed anywhere w.r.t. ${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{1}!m_{3}}$ and ${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{2}?m_{3}}$ .

2.2 Basic interactions

Interactions can be drawn as "sequence diagrams" of which an example is given in the left of Fig.1. Lifelines are drawn as vertical lines. Emission and reception actions are drawn as horizontal arrows carrying the transmitted message and which respectively exit the emitting lifeline or point towards the receiving lifeline. When a direct emission-reception causality can be identified we draw both actions as a single arrow from the emitter towards the receiver.

The top to bottom direction relates to the passing of time. An action (arrow) drawn above another generally occurs beforehand. This scheduling of actions corresponds to the weak sequencing operator. By contrast, strict sequencing may be used to enforce precedence relations between actions occurring on different lifelines. In Fig.1, the arrow carrying $m_{1}$ and specifying its passing between $l_{1}$ and $l_{3}$ is modelled by the interaction $strict({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}},{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{3}?m_{1}})$ . The fact that this arrow stands above that carrying $m_{2}$ can be modelled using the weak sequencing operator: $seq(strict({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}},{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{3}?m_{1}}),strict({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{1}!m_{2}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{2}}))$ . Using $seq$ here instead of $strict$ allows for instance ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{2}}$ to occur before ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{3}?m_{1}}$ even though the latter is drawn above. However ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{1}!m_{2}}$ cannot occur before ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}$ because they both occur on $l_{1}$ .

Parallel and alternative compositions can also be used to specify more complex behavior. On Fig.1, the passing of $m_{3}$ and the emission of $m_{4}$ are scheduled using parallel composition. In the diagram representation this corresponds to the box labelled with "par". This can be modelled with the term $par(strict({\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{1}!m_{3}},{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{2}?m_{3}}),{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}l_{1}!m_{4}})$ . Actions scheduled with $par$ can occur in any order w.r.t. one another. Here, ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}l_{1}!m_{4}}$ can occur before ${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{1}!m_{3}}$ , after ${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{2}?m_{3}}$ or in between those two actions. Alternative composition proposes an exclusive non-deterministic choice between behaviors. Like $par$ , $alt$ is drawn as a box labelled with "alt".

Refer to caption — Figure 1: Example of a basic interaction & its trace semantics

3 Repetition operators in the semantic domain

Scheduling operators define compositions of traces obtained from enabling or forbidding the reordering of actions according to some scheduling policy. All three are associative (in addition, $||$ is commutative) and admit $\{\epsilon\}$ as a neutral element. As a result, we can define (Kleene) closures of those operators to specify repetitions.

Definition 3.1 (Kleene closures).

For any $\diamond\in\{;,\leavevmode\nobreak\ ;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}},\leavevmode\nobreak\ ||\}$ and any $T\in\mathcal{P}(\mathbb{T}_{\Omega})$ ,

the Kleene closure $T^{\diamond*}$ of $T$ is defined by:

\left\{\begin{array}[]{lclr}T^{\diamond 0}&=&\{\epsilon\}&\\ T^{\diamond j}&=&T\diamond T^{\diamond(j-1)}&\textbf{for }j>0\\ T^{\diamond*}&=&\bigcup_{\begin{subarray}{c}j\in\mathbb{N}\end{subarray}}T^{\diamond j}&\end{array}\right.

The three Kleene closures $\leavevmode\nobreak\ {}^{;*}$ , $\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}$ and $\leavevmode\nobreak\ {}^{||*}$ are respectively called, strict, weak and interleaving Kleene closures.

Within the K-closure $T^{\diamond*}$ we can find traces obtained from the repetition (using $\diamond$ as a scheduler) of any number of traces of $T$ . In the example from Fig.2 we consider a set $T$ containing two traces ${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}}$ and ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{1}}$ . The first 3 powersets of $T$ (i.e. $T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}0}\cup T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}1}\cup T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}2}$ ) are displayed, the rest of the weak K-closure of $T$ (i.e. $T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}$ ) is represented by the $\cdots$ .

\left\{\begin{array}[]{l}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}},\\ {\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{1}}\end{array}\right\}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}=\left\{\begin{array}[]{lclcl}\begin{array}[]{l}\epsilon,\\ {\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}},\\ {\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{1}},\end{array}&\nobreak\leavevmode\hfil&\begin{array}[]{l}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}},\\ {\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}},\\ {\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}}.{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{1}},\\ {\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{1}}.{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{1}},\\ {\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}},\\ {\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}!m_{1}}.{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}?m_{1}}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{2}!m_{2}},\\ \end{array}&\nobreak\leavevmode\hfil&\begin{array}[]{l}\cdots\end{array}\end{array}\right\}

Figure 2: Example illustrating the weak Kleene closure

Let us remark a useful property of the K-closures which is that $T\diamond T^{\diamond*}=T^{\diamond*}$ .

Given a scheduling operator $\diamond\in\{;,\leavevmode\nobreak\ ;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}},\leavevmode\nobreak\ ||\}$ whenever $a.t\in T_{1}\diamond T_{2}$ (with $a$ and $t$ any action and trace and $T_{1}$ and $T_{2}$ any sets of traces), it may be so that action $a$ is taken from a trace $a.t^{\prime}$ that belongs to either $T_{1}$ or $T_{2}$ . In Def.3.2, we define restricted versions of the scheduling operators so as to impose action $a$ to be taken from $T_{1}$ .

Definition 3.2 (Restricted scheduling operators).

T_{1}\diamond^{\Lsh}T_{2}=\left\{\leavevmode\nobreak\ t\in T_{1}\diamond T_{2}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\ (t=a.t^{\prime})\Rightarrow(\exists\leavevmode\nobreak\ t_{1}\in\mathbb{T}_{\Omega},\text{ s.t. }(a.t_{1}\in T_{1})\leavevmode\nobreak\ \wedge\leavevmode\nobreak\ (t\in\{t_{1}\}\diamond T_{2}))\leavevmode\nobreak\ \right\}

As an example, given $T_{1}=\{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{1}!m}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}?m}\}$ and $T_{2}=\{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}l_{2}!m}\}$ , we have:

\begin{array}[]{ccc}T_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}T_{2}=\left\{\begin{array}[]{l}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{1}!m}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}?m}.{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}l_{2}!m},\\ {\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{1}!m}.{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}l_{2}!m}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}?m},\\ {\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}l_{2}!m}.{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{1}!m}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}?m}\end{array}\right\}&\leavevmode\nobreak\ \leavevmode\nobreak\ \text{ and }\nobreak\leavevmode\nobreak\leavevmode&T_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}T_{2}=\left\{\begin{array}[]{l}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{1}!m}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}?m}.{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}l_{2}!m},\\ {\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{1}!m}.{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}l_{2}!m}.{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}l_{1}?m}\end{array}\right\}\end{array}

We use the restriction on operators to define Head-First closures (abbr. HF-closure) of scheduling operators in Def.3.3.

Definition 3.3 (Head-first closures).

In the following we will show that HF-closure and K-closure are equivalent for ; and $||$ but that this is not the case for $;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ .

Lemma 3.4.

For any $\diamond\in\{;,\leavevmode\nobreak\ ||\}$ , $T\in\mathcal{P}(\mathbb{T}_{\Omega})$ , $t$ in $\mathbb{T}_{\Omega}$ and $a\in\mathbb{A}_{\Omega}$ we have:

(a.t\in T^{\diamond*})\Rightarrow\left(\exists\leavevmode\nobreak\ t^{\prime}\in\mathbb{T}_{\Omega}\text{ s.t. }(a.t^{\prime}\in T)\wedge\leavevmode\nobreak\ (t\in\{t^{\prime}\}\diamond T^{\diamond*})\right)

Proof 3.5.

By induction on $j$ given $a.t\in T^{\diamond j}$ . In the case of $||$ we use its commutativity.

Lemma 3.6 (Equivalence of HF & K closures for ; & $||$ ).

For any set of traces $T$ :

\begin{array}[]{ccc}T^{;^{\Lsh}*}=T^{;*}&\leavevmode\nobreak\ \leavevmode\nobreak\ \text{ and }\nobreak\leavevmode\nobreak\leavevmode&T^{||^{\Lsh}*}=T^{||*}\end{array}

Proof 3.7.

By induction on a member trace $t$ .

Let us detail a counter example showing that the weak K-closure $\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}$ and the weak HF-closure $\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ are not equivalent. Given $T=\{l_{1}!m_{1}.l_{2}?m_{1},\leavevmode\nobreak\ l_{2}!m_{2}\}$ , let us consider the powerset $T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}2}$ of $T$ . By definition, $\{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}!m_{2}}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{1}!m_{1}}.{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{2}?m_{1}}\}\subset T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}2}$ . Here we can choose to take ${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{1}!m_{1}}$ as a first action and therefore $t={\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{1}!m_{1}}.{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}l_{2}!m_{2}}.{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}l_{2}?m_{1}}\in T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}2}$ . However, $t\not\in T;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}T=T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}2}$ . Also, we have $t\not\in T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}j}$ for any $j$ smaller or greater that $2$ . This can be explained by not having the correct actions and/or not the right numbers of actions to reconstitute $t$ . As a result $t\not\in T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ and hence $T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}\not\subseteq T^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ . This example will be further illustrated in Sec.5.4 with the help of the operational semantics.

4 Syntax & denotational semantics

Interactions terms are defined inductively. Basic building blocks include the empty interaction $\varnothing$ which specifies the empty behavior $\epsilon$ (observation of no action) and any atomic action $a$ , which specifies the single-element trace $a$ (observation of $a$ ). More complex behavior can then be specified inductively using:

•

binary constructors, which are $strict$ , $seq$ , $par$ and $alt$ (introduced in Sec.2.2)
•

unary constructors, which are $loop_{X}$ (the strict loop), $loop_{H}$ (the head loop up to the weak sequencing operator), $loop_{S}$ (the weak loop) and $loop_{P}$ (the parallel loop)

Definition 4.1 (Interaction Language).

We denote by $\mathbb{I}_{\Omega}$ the set of terms inductively defined by the set of operation symbols $\mathcal{F}=\mathcal{F}_{0}\cup\mathcal{F}_{1}\cup\mathcal{F}_{2}$ s.t.:

•

symbols or arity $0$ (constants) are $\mathcal{F}_{0}=\{\varnothing\}\cup\mathbb{A}_{\Omega}$
•

symbols of arity $1$ are $\mathcal{F}_{1}=\{loop_{X},\leavevmode\nobreak\ loop_{H},\leavevmode\nobreak\ loop_{S},\leavevmode\nobreak\ loop_{P}\}$
•

symbols of arity $2$ are $\mathcal{F}_{2}=\{strict,\leavevmode\nobreak\ seq,\leavevmode\nobreak\ par,\leavevmode\nobreak\ alt\}$

In Def.4.1 we define our Interaction Language (IL) as a set of terms $\mathbb{I}_{\Omega}$ inductively defined from $\mathcal{F}$ a finite set of symbols provided with arity in $\mathbb{N}$ . The set of sets of traces $\mathcal{P}(\mathbb{T}_{\Omega})$ admits the structure of a $\mathcal{F}$ -algebra using operators introduced in Sec.2 and Sec.3. The denotational semantics of interactions is then defined in Def.4.2 using the initial homomorphism associated to this $\mathcal{F}$ -algebra.

Definition 4.2 (Denotational semantics).

$\mathcal{A}=(\mathcal{P}(\mathbb{T}_{\Omega}),\leavevmode\nobreak\ \{f^{\mathcal{A}}\leavevmode\nobreak\ |\leavevmode\nobreak\ f\in\mathcal{F}\})$ is the $\mathcal{F}$ -algebra defined by its carrier $\mathcal{P}(\mathbb{T}_{\Omega})$ and the following interpretations of the operation symbols in $\mathcal{F}$ :

\begin{array}[]{ccccc}\begin{array}[]{lcl}\varnothing^{\mathcal{A}}&=&\{\epsilon\}\\ a^{\mathcal{A}}&=&\{a\}\end{array}&\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode\hfil&\begin{array}[]{lcl}strict^{\mathcal{A}}&=&;\\ seq^{\mathcal{A}}&=&;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\\ par^{\mathcal{A}}&=&||\\ alt^{\mathcal{A}}&=&\cup\end{array}&\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode\hfil&\begin{array}[]{lcl}loop_{X}^{\mathcal{A}}&=&\leavevmode\nobreak\ {}^{;*}\\ loop_{H}^{\mathcal{A}}&=&\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}\\ loop_{S}^{\mathcal{A}}&=&\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}\\ loop_{P}^{\mathcal{A}}&=&\leavevmode\nobreak\ {}^{||*}\end{array}\end{array}

The denotational semantics $\sigma_{d}$ of $\mathbb{I}_{\Omega}$ is the unique $\mathcal{F}$ -homomorphism $\sigma_{d}:\mathbb{I}_{\Omega}\rightarrow\mathcal{P}(\mathbb{T}_{\Omega})$ between the free term $\mathcal{F}$ -algebra²²2The free term $\mathcal{F}$ -algebra is defined by its carrier $\mathbb{I}_{\Omega}$ and by interpreting operation symbols of $\mathcal{F}$ as constructors of new terms: for $f\in\mathcal{F}$ of arity $j$ , for $t_{1},\ldots t_{j}\in\mathbb{I}_{\Omega}$ , $f(t_{1},\ldots t_{j})$ is interpreted as itself. $\mathcal{T}_{\mathcal{F}}$ and $\mathcal{A}$ .

The semantics of constants $\varnothing$ and $a\in\mathbb{A}_{\Omega}$ are sets containing a single element being respectively $\{\epsilon\}$ and $\{a\}$ . The $strict$ , $seq$ , $par$ and $alt$ symbols are respectively associated to the ;, $;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ , $||$ and union $\cup$ operators on sets of traces. Their use is shown on Fig.1. On the right of Fig.1, we detail the semantics of the interaction drawn on the left. The resulting set of traces is given on the bottom right. $loop_{X}$ , $loop_{H}$ , $loop_{P}$ , $loop_{S}$ are semantically distinct (as shown on simple examples in [13]). From a system designer perspective, using either loop is motivated by different goals:

•

With $loop_{X}(i)$ , each existing instance of a repeatable behavior (specified by $i$ ) must be executed entirely before any other can start. This implies that, at any given moment there can only exists zero or a single instance. $loop_{X}$ can therefore be used to specify some critical repeatable behavior of which there can only exist one instance at a time.
•

With $loop_{P}(i)$ , all existing instances can be executed concurrently w.r.t. one another, and, at any given moment, new instances can be created. $loop_{P}$ can therefore be used to specify protocols in which any number of new sessions can be created and run in parallel.
•

With $loop_{S}(i)$ , new instances can be created whenever the action triggering the instantiation occurs on a lifeline which is not occulted by previous instances. This can be roughly explained as follows: (1) on each individual lifeline only one instance can be active and (2) given that, for any such instance, a lifeline might "have finished" before the others then it is allowed to start another instance. $loop_{S}$ can therefore be used to specify repeatable behaviors that are sequential but that have no enforced synchronization mechanisms.
•

The head loop $loop_{H}$ is associated to the weak HF-closure operator $\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ which is an ad-hoc algebraic artifact and not a K-closure. We include it in our IL because it might correspond to a more intuitive understanding of sequential loops than $loop_{S}$ , as illustrated in Sec.5.4.

5 A structural operational semantics

In this section we present a structural operational semantics for interactions in the style of process calculus [2]. It relies on the definition (by structural induction) of two predicates: " $i\downarrow$ " (the termination predicate) indicates that interaction term $i$ accepts the empty trace and " $i\xrightarrow{a}i^{\prime}$ " (the execution relation) indicates that traces $a.t$ such that $t$ is accepted by $i^{\prime}$ are accepted by $i$ . We define $\downarrow$ in Sec.5.1. The relation $\rightarrow$ allows the determination, for any interaction $i$ , of which actions $a$ can be immediately executed, and, of potential follow-up interactions $i^{\prime}$ which express continuations $t$ of traces $a.t$ accepted by $i$ . Defining an execution relation $\rightarrow$ is a staple of process calculus [2]. However, as we want to define such a similar relation $\rightarrow$ for our IL, particular care is needed when dealing with weak sequencing. Hence we introduce intermediate notions in Sec.5.2 before defining $\rightarrow$ in Sec.5.3.

5.1 Termination

By reasoning on the structure of an interaction term $i$ , we can determine whether or not the empty trace $\epsilon$ belongs to its semantics. When this holds, we say that $i$ terminates and use the notation $i\downarrow$ as in [2]. $\downarrow$ is defined as an inductive predicate in Def.5.1 and its characterization w.r.t. the semantics $\sigma_{d}$ of interactions is given in Lem.5.2.

Definition 5.1 (Termination).

The predicate $\downarrow\subset\mathbb{I}_{\Omega}$ is s.t. for any $i_{1}$ and $i_{2}$ from $\mathbb{I}_{\Omega}$ , any $f\in\{strict,seq,par\}$ and any $k\in\{X,H,S,P\}$ we have:

$\top$ $\varnothing\downarrow$

$i_{1}\downarrow$ $alt(i_{1},i_{2})\downarrow$

$i_{2}\downarrow$ $alt(i_{1},i_{2})\downarrow$

$i_{1}\downarrow$ $i_{2}\downarrow$ $f(i_{1},i_{2})\downarrow$

$\top$ $loop_{k}(i_{1})\downarrow$

All rules of Def.5.1 are evident. The empty interaction $\varnothing$ only accepts $\epsilon$ , and thus terminates. An interaction with a loop at its root terminates because it is possible to repeat zero times its content. As $alt(i_{1},i_{2})$ specifies a choice, it terminates iff either $i_{1}$ or $i_{2}$ terminates. An interaction of the form $f(i_{1},i_{2})$ , with $f$ being a scheduling constructor, terminates iff both $i_{1}$ and $i_{2}$ terminate.

Lemma 5.2 (Termination w.r.t. $\sigma_{d}$ ).

For any $i\in\mathbb{I}_{\Omega}$ we have $(i\downarrow)\Leftrightarrow(\epsilon\in\sigma_{d}(i))$

Proof 5.3.

By induction on the term structure of interactions.

5.2 Dealing with weak-sequencing using evasion & pruning

Weak sequencing only allows interleavings between actions that occur on different lifelines. As a result, within an interaction of the form $i=seq(i_{1},i_{2})$ , some actions that can be executed in $i_{2}$ may also be executed in $seq(i_{1},i_{2})$ . In other words, given a trace $a.t\in\sigma_{d}(i)$ , action $a$ might correspond to an action expressed by $i_{2}$ . This is however conditioned by the ability of $i_{1}$ to express traces that have no conflict w.r.t. $a$ so that $a$ may be placed in front of what is expressed by $i_{1}$ when recomposing $a.t$ .

In the previous section we have seen that the termination predicate $i\downarrow$ states that interaction $i$ is able to express the empty trace. We define "evasion" as a similar, although weaker, notion than "termination" that can be described as a form of local termination. For a lifeline $l$ , we say that $i$ evades $l$ , denoted by $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ , if $i$ accepts at least one trace that does not contain actions occurring on $l$ . Evasion is defined inductively in Def.5.4. For any $i\in\mathbb{I}_{\Omega}$ and $l\in L$ , it is always decidable whether $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ or $\neg(i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l)$ . We may then denote by $i\not{\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}l$ the fact that $\neg(i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l)$ and say that $i$ collides with $l$ .

Definition 5.4 (Evasion).

The predicate $\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\subset\mathbb{I}_{\Omega}\times L$ is s.t. for any $i_{1}$ and $i_{2}$ from $\mathbb{I}_{\Omega}$ , any $l\in L$ , any $a\in\mathbb{A}_{\Omega}$ , any $f\in\{strict,seq,par\}$ and any $k\in\{X,H,S,P\}$ we have:

$\theta(a)\neq l$ $\varnothing\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$

$\theta(a)\neq l$ $a\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$

$i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ $alt(i_{1},i_{2})\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$

$i_{2}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ $alt(i_{1},i_{2})\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$

$i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ $i_{2}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ $f(i_{1},i_{2})\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$

$loop_{k}(i_{1})\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$

The empty interaction $\varnothing$ evades any lifeline as $\epsilon$ contains no action. An interaction reduced to a single action $a$ evades $l$ iff $a$ does not occur on $l$ . As for termination, an interaction with a loop at its root evades any lifeline because it accepts $\epsilon$ . Choice and scheduling operators are also handled in the same manner as for the termination predicate.

Lemma 5.5 (Evasion w.r.t. $\sigma_{d}$ ).

For any $l\in L$ and $i\in\mathbb{I}_{\Omega}$ , $(i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l)\Leftrightarrow(\exists\leavevmode\nobreak\ t\in\sigma_{d}(i),\neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l))$

Proof 5.6.

By induction on the term structure of interactions.

Let us remark that, for any $i\in\mathbb{I}_{\Omega}$ , if $i\downarrow$ then $\forall\leavevmode\nobreak\ l\in L$ , $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ . Indeed, $\epsilon$ has no conflict w.r.t. any $l$ . However the opposite does not hold: it suffices to consider $L=\{l_{1},l_{2}\}$ and $i=alt(l_{1}!m,l_{2}!m)$ and observe that $\forall\leavevmode\nobreak\ l\in L$ , $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ holds while $i\downarrow$ does not.

The application of the evasion predicate (w.r.t. lifeline $l_{2}$ ) is illustrated on Fig.3. On the right is represented the syntaxic structure of an interaction $i$ , and, on the left, the corresponding drawing as a sequence diagram. On the syntax tree, the nodes are decorated with symbols \faCheckCircle to signify that the sub-interaction underneath that node evades $l_{2}$ or \faTimesCircle to indicate that this is not the case (i.e. that it collides with $l_{2}$ ). Starting from the leaves we can decorate all nodes and conclude once the root is reached. By taking the right branch of the alternative and by choosing not to instantiate the loop, we can see that $i$ accepts some traces that have no conflict w.r.t. lifeline $l_{2}$ (in our case, only the trace $l_{3}!m_{2}.l_{1}?m_{2}$ ). As a result the interaction $i$ verifies $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l_{2}$ . On the diagram representation, evasion can be illustrated by drawing a line over the lifeline of interest. This line can be decomposed into several segments that correspond to specific areas of the diagram (operands) and that are colored either in green or in red. The coloration of the segment depends on whether the sub-interaction corresponding to the operand evades or collides with the lifeline of interest.

With evasion we can determine whether or not an action $a$ that is executable in $i_{2}$ i.e. s.t. $i_{2}\xrightarrow{a}i_{2}^{\prime}$ is also executable in $i=seq(i_{1},i_{2})$ . However, this is not enough to define a rule $seq(i_{1},i_{2})\xrightarrow{a}i^{\prime}$ which is compatible with the semantics $\sigma_{d}$ . $i^{\prime}$ must specify continuations $t$ s.t. $a.t\in\sigma_{d}(i)$ . By definition of $\sigma_{d}$ , continuation traces $t$ have to be build from traces $t_{1}\in\sigma_{d}(i_{1})$ and $t_{2}$ such that $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ and $a.t_{2}\in\sigma_{d}(i_{2})$ . By defining $i_{1}^{\prime}$ as the interaction which expresses exactly those traces $t_{1}$ s.t. $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ we may produce a rule $seq(i_{1},i_{2})\xrightarrow{a}seq(i_{1}^{\prime},i_{2}^{\prime})$ that is compatible with $\sigma_{d}$ . The computation of $i_{1}^{\prime}$ is ensured by a process that we call pruning.

Pruning is defined as an inductive relation $\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\longrightarrow$ s.t. $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i^{\prime}$ indicates that the pruning of $i\in\mathbb{I}_{\Omega}$ w.r.t. $l\in L$ yields $i^{\prime}\in\mathbb{I}_{\Omega}$ . Pruning is defined so has to preserve "a maxima" the original semantics of $i$ so that $\sigma_{d}(i^{\prime})\subseteq\sigma_{d}(i)$ is the maximum subset of $\sigma_{d}(i)$ that contains no trace conflicting with $l$ (see Lem.5.10).

Definition 5.7 (Pruning).

The pruning relation $\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\longrightarrow\subset\mathbb{I}_{\Omega}\times L\times\mathbb{I}_{\Omega}$ is s.t. for any $l\in L$ , any $f\in\{strict,seq,par\}$ and any $k\in\{X,H,S,P\}$ :

$\varnothing\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}\varnothing$

$\theta(a)\neq l$ $a\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}a$

$i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{1}^{\prime}$ $i_{2}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{2}^{\prime}$ $f(i_{1},i_{2})\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}f(i_{1}^{\prime},i_{2}^{\prime})$

$i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{1}^{\prime}$ $i_{2}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{2}^{\prime}$ $alt(i_{1},i_{2})\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}alt(i_{1}^{\prime},i_{2}^{\prime})$

$i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{1}^{\prime}$ $i_{2}\not{\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}l$ $alt(i_{1},i_{2})\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{1}^{\prime}$

$i_{2}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{2}^{\prime}$ $i_{1}\not{\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}l$ $alt(i_{1},i_{2})\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{2}^{\prime}$

$i_{1}\not{\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}l$ $loop_{k}(i_{1})\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}\varnothing$

Let us immediately remark that evasion and pruning are intertwined notions. Indeed, as per Lem.5.8 evasion is equivalent to the existence and unicity of a pruned interaction. We could define pruning without evasion. However, so as to draw parallels w.r.t. the termination predicate and in order to separate concerns and ease the understanding of proofs we have defined both notions separately.

Lemma 5.8 (Conditional existence & unicity for pruning).

For any $i\in\mathbb{I}_{\Omega}$ and any $l\in L$ :

(i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l)\Leftrightarrow(\exists!\leavevmode\nobreak\ i^{\prime}\in\mathbb{I}_{\Omega}\text{ s.t. }i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i^{\prime})

Proof 5.9.

Immediate, by induction on the term structure of interactions.

Let us comment on the rules defining the pruning relation. We have $\varnothing\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}\varnothing$ because the semantics of $\varnothing$ being $\{\epsilon\}$ , there are no conflicts w.r.t. $l$ . Any action $a\in\mathbb{A}_{\Omega}$ is prunable iff $\theta(a)\neq l$ . In such a case, $a$ needs not be eliminated and thus $a\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}a$ . For $i=alt(i_{1},i_{2})$ to be prunable we must have either or both of $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ or $i_{2}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ . If both branches evade $l$ they can be pruned and kept as alternatives in the new interaction term. If only a single one does, we only keep the pruned version of this single branch. For any scheduling constructor $f$ , if $i=f(i_{1},i_{2})$ , in order to have $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ we must have both $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ and $i_{2}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ . In that case the unique interaction $i^{\prime}$ such that $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i^{\prime}$ is simply defined as the scheduling, using $f$ , of the pruned versions of $i_{1}$ and $i_{2}$ . Finally, for loops, i.e. $i=loop_{k}(i_{1})$ with $k\in\{X,H,S,P\}$ , we distinguish two cases: (a) if $i_{1}\not\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ then any execution of $i_{1}$ will yield a trace conflicting $l$ . Therefore it is necessary to forbid repetition; (b) if $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ then it is not necessary to forbid repetition, given that $i_{1}$ can be pruned as $i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{1}^{\prime}$ with $i_{1}^{\prime}$ not expressing traces conflicting $l$ . This being the modification which preserves a maximum amount of traces, we have $loop_{k}(i_{1})\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}loop_{k}(i_{1}^{\prime})$ .

We have seen that the interaction $i$ of Fig.3 satisfies $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l_{2}$ . Therefore Lem.5.8 implies the existence of a unique $i^{\prime}$ s.t. $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l_{2}}i^{\prime}$ . Fig.4 illustrates the computation of $i^{\prime}$ . The blue lines represent the modifications in the syntax of $i$ that occur during its pruning into $i^{\prime}$ . On Fig.3 we decorated sub-interactions of $i$ with \faTimesCircle whenever they did not evade $l_{2}$ . During pruning, those sub-interactions must be eliminated given that the resulting term must not express actions occurring on $l_{2}$ . Hence, on Fig.4, we have crossed in blue the problematic sub-interactions. The root node is an $alt$ . Let us note $i=alt(i_{1},i_{2})$ . On Fig.3 we have seen that we have $i_{1}\not{\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}l_{2}$ and $i_{2}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l_{2}$ . Therefore we have $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l_{2}}i_{2}^{\prime}$ with $i_{2}^{\prime}$ being such that $i_{2}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l_{2}}i_{2}^{\prime}$ . This selection of the right branch of the $alt$ is illustrated on Fig.4 by the curved arrow which "replaces" the $alt$ by the $seq$ on its bottom right. There remains to determine $i_{2}^{\prime}$ s.t. $i_{2}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l_{2}}i_{2}^{\prime}$ . At the root of $i_{2}$ we have a $seq$ . Let us note $i_{2}=seq(i_{A},i_{B})$ . As per Fig.3 we have both $i_{A}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l_{2}$ and $i_{B}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l_{2}$ and therefore $i_{2}^{\prime}=seq(i_{A}^{\prime},i_{B}^{\prime})$ such that $i_{A}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l_{2}}i_{A}^{\prime}$ and $i_{B}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l_{2}}i_{B}^{\prime}$ . Underneath $i_{A}$ , no actions occur on $l_{2}$ and hence $i_{A}^{\prime}=i_{A}$ . At the root of $i_{B}$ we have a $loop_{X}$ . Let us note $i_{B}=loop_{X}(i_{C})$ . As per Fig.3 we have $i_{C}\not{\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}l_{2}$ and therefore $i_{B}^{\prime}=\varnothing$ which is illustrated on Fig.4 by the ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\leftarrow\varnothing}$ in blue, which "replaces" the $loop_{X}$ by $\varnothing$ . Finally there remain $i^{\prime}=seq(i_{A},\varnothing)$ , which is drawn as a SD on the right of Fig.4.

Lem.5.10 states that given $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i^{\prime}$ , the pruned interaction $i^{\prime}$ exactly specifies all the executions of $i$ that do not involve $l$ .

Lemma 5.10 (Pruning w.r.t. $\sigma_{d}$ ).

For any $l\in L$ and any $i$ and $i^{\prime}$ from $\mathbb{I}_{\Omega}$ :

(i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i^{\prime})\Rightarrow(\sigma_{d}(i^{\prime})=\{t\in\sigma_{d}(i)\leavevmode\nobreak\ |\leavevmode\nobreak\ \neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)\})

Proof 5.11.

By induction on the term structure of interactions.

In the next section we make use of pruning so as to formally define an execution relation $\rightarrow$ for our IL and we use it to formulate a structural operational semantics in the style of process algebra.

5.3 Execution relation & operational semantics

A structural operational semantics, presented in the style of Plotkin [17] allows determining accepted traces $t\in\sigma_{d}(i_{1})$ such that $t=a_{1}.\cdots.a_{n}$ through the assertion of a succession of predicates of the form $i_{j}\xrightarrow{a_{j}}i_{j+1}$ representing the evolution of the system. By expressing action $a_{j}$ , the system goes from being modelled by $i_{j}$ to being modelled by $i_{j+1}$ . We present this execution relation " $\rightarrow$ " as an inductive predicate, in a similar fashion as the pruning relation " $\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\longrightarrow$ ".

Definition 5.12 (Execution relation).

The execution relation $\rightarrow\subset\mathbb{I}_{\Omega}\times\mathbb{A}_{\Omega}\times\mathbb{I}_{\Omega}$ is s.t.:

$\xrightarrow{a}$ $a\xrightarrow{a}\varnothing$

$i_{1}\xrightarrow{a}i^{\prime}_{1}$ $alt(i_{1},i_{2})\xrightarrow{a}i^{\prime}_{1}$

$i_{2}\xrightarrow{a}i^{\prime}_{2}$ $alt(i_{1},i_{2})\xrightarrow{a}i^{\prime}_{2}$

$i_{1}\xrightarrow{a}i^{\prime}_{1}$ $par(i_{1},i_{2})\xrightarrow{a}par(i^{\prime}_{1},i_{2})$

$i_{2}\xrightarrow{a}i^{\prime}_{2}$ $par(i_{1},i_{2})\xrightarrow{a}par(i_{1},i^{\prime}_{2})$

$i_{1}\xrightarrow{a}i^{\prime}_{1}$ $strict(i_{1},i_{2})\xrightarrow{a}strict(i^{\prime}_{1},i_{2})$

$i_{2}\xrightarrow{a}i^{\prime}_{2}$ $i_{1}\downarrow$ $strict(i_{1},i_{2})\xrightarrow{a}i^{\prime}_{2}$

$i_{1}\xrightarrow{a}i^{\prime}_{1}$ $seq(i_{1},i_{2})\xrightarrow{a}seq(i^{\prime}_{1},i_{2})$

$i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i_{1}^{\prime}$ $i_{2}\xrightarrow{a}i_{2}^{\prime}$ $seq(i_{1},i_{2})\xrightarrow{a}seq(i_{1}^{\prime},i_{2}^{\prime})$

$i_{1}\xrightarrow{a}i_{1}^{\prime}$ $loop_{X}(i_{1})\xrightarrow{a}strict(i_{1}^{\prime},loop_{X}(i_{1}))$

$i_{1}\xrightarrow{a}i_{1}^{\prime}$ $loop_{H}(i_{1})\xrightarrow{a}seq(i_{1}^{\prime},loop_{H}(i_{1}))$

$i_{1}\xrightarrow{a}i_{1}^{\prime}$ $loop_{S}(i_{1})\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i^{\prime}$ $loop_{S}(i_{1})\xrightarrow{a}seq(i^{\prime},seq(i_{1}^{\prime},loop_{S}(i_{1})))$

$i_{1}\xrightarrow{a}i_{1}^{\prime}$ $loop_{P}(i_{1})\xrightarrow{a}par(i_{1}^{\prime},loop_{P}(i_{1}))$

The formulation of most of the rules is very similar to what can be found in process algebras. The notable differences mainly concern the rules handling weak sequencing and loops. In an interaction reduced to an action $a$ , $a$ may be executed with $a\xrightarrow{a}\varnothing$ so that what remains to be executed is the empty interaction $\varnothing$ . If within $i=alt(i_{1},i_{2})$ , action $a$ can be executed in either $i_{1}$ or $i_{2}$ with either $i_{1}\xrightarrow{a}i_{1}^{\prime}$ or $i_{2}\xrightarrow{a}i_{2}^{\prime}$ then it may be executed in $i$ and the resulting interaction is either $i_{1}^{\prime}$ or $i_{2}^{\prime}$ . For $i=par(i_{1},i_{2})$ , if we have either $i_{1}\xrightarrow{a}i_{1}^{\prime}$ or $i_{2}\xrightarrow{a}i_{2}^{\prime}$ then $a$ may be executed in $i$ and the resulting interaction naturally is either $par(i_{1}^{\prime},i_{2})$ or $par(i_{1},i_{2}^{\prime})$ . Executing actions on the left of either a $strict$ or a $seq$ follow the same rule as in the case of a $par$ because no precedence relations are enforced on the left-hand side. However, it is only possible to execute an action $a$ on the right of $i=strict(i_{1},i_{2})$ if $i_{1}$ terminates. Indeed, in that case $i_{1}$ may express the empty trace $\epsilon$ as per Lem.5.2 and nothing prevents $a$ to be the first action to be executed. The resulting interaction is then $i_{2}^{\prime}$ given that we force $i_{1}$ to express $\epsilon$ . Likewise, within $i=seq(i_{1},i_{2})$ there is a condition for executing an action $a$ on the right. This condition is that $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\theta(a)$ , which, as per Lem.5.8 is implied by the condition $i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i_{1}^{\prime}$ . Given $i_{2}^{\prime}$ s.t. $i_{2}\xrightarrow{a}i_{2}^{\prime}$ we therefore have $i\xrightarrow{a}seq(i_{1}^{\prime},i_{2}^{\prime})$ given that we prune the left sub-interaction and execute the action on the right sub-interaction.

The rules for $loop_{X}$ , $loop_{H}$ and $loop_{P}$ reflect the definitions of the corresponding HF-closures which respectively are $\leavevmode\nobreak\ {}^{;^{\Lsh}*}$ , $\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ and $\leavevmode\nobreak\ {}^{||^{\Lsh}*}$ . Let us indeed consider $(k,\diamond,f)\in\{(X,;,strict),(H,;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}},seq),(P,||,par)\}$ . Whenever $i\xrightarrow{a}i^{\prime}$ we have $loop_{k}(i)\xrightarrow{a}f(i^{\prime},loop_{k}(i))$ . As a result, any $t\in\sigma_{d}(f(i^{\prime},loop_{k}(i)))$ is s.t. $t\in\{t_{1}\}\diamond\sigma_{d}(loop_{k}(i))$ for a certain $t_{1}\in\sigma_{d}(i^{\prime})$ . Given that $a.t_{1}\in\sigma_{d}(i)$ , this corresponds to choosing action $a$ from the first iteration of the loop i.e. $a.t\in\{a.t_{1}\}\diamond^{\Lsh}\sigma_{d}(loop_{k}(i))\subset\sigma_{d}(i)\diamond^{\Lsh}\sigma_{d}(loop_{k}(i))$ , which coincides with using the restricted operator $\diamond^{\Lsh}$ as a scheduler. $loop_{H}$ is explicitly associated to $\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ and thus the formulation of its rule is self-evident. In the case of $loop_{X}$ and $loop_{P}$ it is the fact that the HF and K-closures of ; and $||$ are equivalent (as per Lem.3.6) which enables their respective rules to be formulated in this manner.

The rule for $loop_{S}$ allows for the first action $a$ of a trace $a.t$ to be taken from a later iteration of the loop. Let us consider $i=loop_{S}(i_{1})$ and $a.t\in\sigma_{d}(i)$ . The rule is formulated such that $t\in\sigma_{d}(seq(i^{\prime},seq(i_{1}^{\prime},i)))$ with $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i^{\prime}$ and $i_{1}\xrightarrow{a}i_{1}^{\prime}$ . Indeed, action $a$ is expressed by sub-interaction $i_{1}$ so there exists $i_{1}^{\prime}$ s.t. $i_{1}\xrightarrow{a}i_{1}^{\prime}$ . Also, given that $i$ is a loop, it is always prunable (Lem.5.8) so there exists $i^{\prime}$ s.t. $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i^{\prime}$ . The fact that $t\in\sigma_{d}(seq(i^{\prime},seq(i_{1}^{\prime},i)))$ translates into having $t\in\sigma_{d}(i^{\prime});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i_{1}^{\prime});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i)$ . Then:

•

If $a$ is taken from the first iteration of the loop, then, given that $\epsilon\in\sigma_{d}(i^{\prime})$ (Lem.5.10) we have $t\in\{\epsilon\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{1}^{\prime}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i)$ with $t_{1}^{\prime}$ a continuation of the first iteration s.t. $t_{1}=a.t_{1}^{\prime}\in\sigma_{d}(i_{1})$ .
•

If $a$ is taken from the second iteration of the loop, let us consider $t_{1}\in\sigma_{d}(i_{1})$ the first iteration and $t_{2}=a.t_{2}^{\prime}\in\sigma_{d}(i_{1})$ the second one (from which $a$ is taken and hence $t_{2}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ ). We then have $t\in\{t_{1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{2}^{\prime}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i)$ and the condition $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ . This condition implies, as per Lem.5.10 that $\{t_{1}\}\subset\sigma_{d}(i^{\prime})$ .
•

The reasoning is the same when $a$ is taken from later instances. Let us indeed consider $a.t\in\{t_{1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{n-1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{n}^{\prime}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i)$ . We then have $\{t_{1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{n-1}\}\subset\sigma_{d}(i^{\prime})$ because $i^{\prime}$ is either a loop (and therefore absorbing) or the empty interaction (in that degenerate case all the $t_{j}$ are $\epsilon$ ) and hence the rules indeed allows $a$ to be taken from any iteration.

Definition 5.13 (Operational semantics).

$\sigma_{o}:\mathbb{I}_{\Omega}\rightarrow\mathcal{P}(\mathbb{T}_{\Omega})$ is s.t.:

$i\downarrow$ $\epsilon\in\sigma_{o}(i)$

$t\in\sigma_{o}(i^{\prime})$ $i\xrightarrow{a}i^{\prime}$ $a.t\in\sigma_{o}(i)$

This execution relation then constitutes the small steps of the operational semantics $\sigma_{o}$ that we define in Def.5.13.

5.4 Illustrative example

On Fig.5 we illustrate both the operational semantics and the counter-example from Sec.3 showcasing the difference between $loop_{H}$ and $loop_{S}$ . We consider repetitions of $i=alt(strict(l_{1}!m_{1},l_{2}?m_{1}),l_{2}!m_{2})$ . On the first row we illustrate the construction of a trace accepted by $seq(i,i)$ where $i$ is repeated twice using weak sequencing. Here, the second occurrence of action $l_{1}!m_{1}$ (at the bottom) is immediately executable because, with pruning, we can force the choice of the right branch of the first alternative which evades $l_{1}$ . From that point on the execution of the remainder is straightforward, and, in total, we can conclude that the trace $t=l_{1}!m_{1}.l_{2}!m_{2}.l_{2}?m_{1}$ is expressed by $seq(i,i)$ . Now, if we were to try to reproduce this behavior using $loop_{H}$ to repeat $i$ (i.e. with $loop_{H}(i)$ ) we would get what is illustrated on the second row of Fig.5. We can manage to execute the first action $l_{1}!m_{1}$ but from that point, the second action of $t$ which is $l_{2}!m_{2}$ is not executable. Indeed, the presence of $l_{2}?m_{1}$ at the top of the diagram prevents it to be executed. As we have indicated earlier (and by definition) $loop_{H}$ is associated to the weak HF-closure $\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ and not to the K-closure $\leavevmode\nobreak\ {}^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}$ . It is therefore expected that $t$ could not be accepted by $loop_{H}(i)$ in this example. However, as illustrated on the third row of Fig.5, $loop_{S}(i)$ can recognize $t$ . The addition of the pruned version of the loop allows one to delay the determination of the instance as part of which the initial $l_{1}!m_{1}$ is executed. In this case, the pruned loop is instanciated once, which means that $l_{1}!m_{1}$ was part of the second instance.

6 Proving the equivalence of both semantics

In the following we formally prove the equivalence of $\sigma_{o}$ and $\sigma_{d}$ . Details of the proofs are available in the appendix and a formalisation using Coq is available in [11].

Let us at first prove that for any interaction $i$ we have $\sigma_{o}(i)\subset\sigma_{d}(i)$ . The first step to do so is to characterize the execution relation " $\rightarrow$ " w.r.t. $\sigma_{d}$ , which we do in Lem.6.1.

Lemma 6.1 (Property 1 of $\rightarrow$ w.r.t. $\sigma_{d}$ ).

For any $a\in\mathbb{A}_{\Omega}$ , $t\in\mathbb{T}_{\Omega}$ and $i$ and $i^{\prime}$ from $\mathbb{I}_{\Omega}$ :

\left(\begin{array}[]{c}(i\xrightarrow{a}i^{\prime})\wedge(t\in\sigma_{d}(i^{\prime}))\end{array}\right)\Rightarrow(a.t\in\sigma_{d}(i))

Proof 6.2.

By induction on the 13 cases that makes the hypothesis $i\xrightarrow{a}i^{\prime}$ possible.

We then remark that Lem.6.1 and Lem.5.2 state that the $\sigma_{d}$ semantics accepts the same two construction rules (that for the empty trace $\epsilon$ and that for non empty traces of the form $a.t$ ) as those that define $\sigma_{o}$ inductively. As a result any trace that might be accepted according to $\sigma_{o}$ must also be accepted according to $\sigma_{d}$ . This implies the inclusion from Th.6.3.

Theorem 6.3 (Inclusion of $\sigma_{o}$ in $\sigma_{d}$ ).

For any $i\in\mathbb{I}_{\Omega}$ we have $\sigma_{o}(i)\subset\sigma_{d}(i)$

Proof 6.4.

By induction on a member trace $t$ .

Let us now prove the reciprocate, i.e. that for any interaction $i$ , $\sigma_{d}(i)\subset\sigma_{o}(i)$ . As in the previous case, we provide, with Lem.6.5, a characterization of " $\rightarrow$ " w.r.t. $\sigma_{d}$ . Lem.6.5 is, in a certain manner, the reciprocate of Lem.6.1.

Lemma 6.5 (Property 2 of $\rightarrow$ w.r.t. $\sigma_{d}$ ).

For any $a\in\mathbb{A}_{\Omega}$ , $t\in\mathbb{T}_{\Omega}$ and $i\in\mathbb{I}_{\Omega}$ :

(a.t\in\sigma_{d}(i))\Rightarrow\left(\exists\leavevmode\nobreak\ i^{\prime}\in\mathbb{I}_{\Omega},\leavevmode\nobreak\ \begin{array}[]{c}(i\xrightarrow{a}i^{\prime})\wedge(t\in\sigma_{d}(i^{\prime}))\end{array}\right)

Proof 6.6.

By induction on the term structure of interactions.

Thanks to Lem.6.5 and the characterization from Lem.5.2 we conclude with Th.6.7.

Theorem 6.7 (Inclusion of $\sigma_{d}$ in $\sigma_{o}$ ).

For any $i\in\mathbb{I}_{\Omega}$ we have $\sigma_{d}(i)\subset\sigma_{o}(i)$

Proof 6.8.

By induction on a member trace $t$ .

We have therefore proven both inclusion and can conclude that the operational semantics $\sigma_{o}$ is indeed equivalent to the denotational-style semantics $\sigma_{d}$ .

7 Related works

The main inspiration for the syntax & denotational semantics of our IL is [7]. In [7], a semantics for interactions is formulated using operators on sets of traces. However, loops are not handled. In [14], an operational semantics for MSC is presented. Similarities between [14] and our work notably include the use of pruning which, in [14], relates to a "permission relation". However we have some major distinctions concerning which constructors are defined and how they are handled by rules of the semantics. In [14] loops are not handled and there is no $strict$ constructor. Indeed, causal relations between actions occurring on different lifelines (e.g. emission-reception) are handled by maps that are updated during execution. In [15] a survey of formal semantics associated to UML-SDs is proposed. It is notable that UML-SDs are described semi-formally in the norm [16]. This allows for a rich language with operators such as $assert$ or $negate$ [5] which are not covered in our IL. However a full formalisation proves difficult, as explained in [15, 5]. As mentioned in the introduction, most approaches rely on translations towards other formalisms [3] or consist in denotational semantics [19] that are most often based on partial order sets. The extent to which UML-SDs are formalised may vary [15]; some works formalize loops [10], others do not [7], and some only allow finitely many iterations [19]. In all cases where there are loops, only one loop operator is proposed and may correspond to either $loop_{H}$ or $loop_{S}$ .

Earlier works of ours [13, 12] focused on the application of the operational semantics for formal verification. In particular we were interested in the static analysis of traces and multi-traces (sets of locally defined traces) against interaction specifications (the membership problem). In those works we have used an "algorithmicized" version of the operational semantics. The inductive predicates for $\downarrow$ , $\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ and the $\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\longrightarrow$ and $\rightarrow$ relations were presented in functional style and we separated concerns between the determination of which actions are immediately executable (uniquely identified by their positions) and the execution of said actions. Novel contributions in this paper w.r.t. [13, 12] consist in the distinction of $loop_{S}$ & $loop_{H}$ , the formulation of the operational semantics in the style of process algebras and the proof of equivalence w.r.t. a denotational semantics (a Coq proof is available in [11]).

8 Conclusion & further work

In this paper we defined an IL for specifying the behavior of distributed and concurrent systems. This language includes weak and strict sequencing, parallel & alternative composition as well as four distinct loop operators to specify different kinds of repetition. We formulate the semantics of this IL: (1) in denotational-style, making use of composition & algebraic operators and (2) in operational-style by reconstructing accepted traces via the succession of atomic executions. The equivalence of both formulations is proven (Coq proof in [11]). As demonstrated in [13, 12], the operational semantics can be further exploited in formal verification techniques such as multi-trace analysis. Other techniques may be explored in further work, such as online testing, monitoring or test generation. In addition, we may also investigate enriching our language with some form of value passing i.e. instead of exchanging abstract messages $m\in M$ we may interpret them concretely or symbolically with typed data. This last point is notably addressed in some process calculi frameworks [6].

References

[1] S. Akshay, Benedikt Bollig, Paul Gastin, Madhavan Mukund, and K. Narayan Kumar. Distributed timed automata with independently evolving clocks. In Franck van Breugel and Marsha Chechik, editors, 19th Conf. on Concurrency Theory (CONCUR), pages 82–97, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
[2] J.C.M. Baeten. Process algebra with explicit termination. Computing science reports. Technische Universiteit Eindhoven, 2000.
[3] Christoph Eichner, Hans Fleischhack, Roland Meyer, Ulrik Schrimpf, and Christian Stehno. Compositional semantics for uml 2.0 sequence diagrams using petri nets. In Andreas Prinz, Rick Reed, and Jeanne Reed, editors, SDL 2005: Model Driven, pages 133–148, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
[4] Serge Haddad and Igor Khmelnitsky. Dynamic recursive petri nets. In Ryszard Janicki, Natalia Sidorova, and Thomas Chatain, editors, Application and Theory of Petri Nets and Concurrency, pages 345–366, Cham, 2020. Springer International Publishing.
[5] David Harel and Shahar Maoz. Assert and negate revisited: Modal semantics for UML sequence diagrams. Software and Systems Modeling, 7(2):237–252, 2008.
[6] Anna Ingólfsdóttir and Huimin Lin. A symbolic approach to value-passing processes. In J.A. Bergstra, A. Ponse, and S.A. Smolka, editors, Handbook of Process Algebra, pages 427–478. Elsevier Science, Amsterdam, 2001. doi:10.1016/B978-044482830-9/50025-4.
[7] Alexander Knapp and Till Mossakowski. UML Interactions Meet State Machines - An Institutional Approach. In 7th Conf. on Algebra and Coalgebra in Computer Science (CALCO), volume 72 of Leibniz International Proceedings in Informatics (LIPIcs), 2017.
[8] Alexander Knapp and Jochen Wuttke. Model checking of uml 2.0 interactions. In Thomas Kühne, editor, Models in Software Engineering, pages 42–51, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.
[9] Kamal Lodaya and Pascal Weil. Series-parallel languages and the bounded-width property. Theor. Comput. Sci., 237(1–2):347–380, April 2000. doi:10.1016/S0304-3975(00)00031-1.
[10] Lunjin Lu and Dae-Kyoo Kim. Required behavior of sequence diagrams: Semantics and conformance. ACM Trans. Softw. Eng. Methodol., 23(2), April 2014. doi:10.1145/2523108.
[11] Erwan Mahe. Coq proof for the equivalence of the semantics. erwanm974.github.io/coq_hibou_label_semantics_equivalence/. Accessed: 2021-04-29.
[12] Erwan Mahe, Boutheina Bannour, Christophe Gaston, Arnault Lapitre, and Pascale Le Gall. A small-step approach to multi-trace checking against interactions. In Proceedings of the 36th Annual ACM Symposium on Applied Computing, SAC ’21, page 1815–1822, New York, NY, USA, 2021. Association for Computing Machinery. doi:10.1145/3412841.3442054.
[13] Erwan Mahe, Christophe Gaston, and Pascale Le Gall. Revisiting semantics of interactions for trace validity analysis. In Heike Wehrheim and Jordi Cabot, editors, Fundamental Approaches to Software Engineering, pages 482–501, Cham, 2020. Springer International Publishing.
[14] Sjouke Mauw and Michel Adriaan Reniers. Operational semantics for msc’96. Computer Networks, 31(17):1785–1799, 1999. doi:10.1016/S1389-1286(99)00060-2.
[15] Zoltán Micskei and Hélène Waeselynck. The many meanings of uml 2 sequence diagrams: a survey. Software & Systems Modeling, 10(4):489–514, 2011.
[16] OMG. Unified Modeling Language v2.5.1. omg.org/spec/UML/2.5.1/PDF, 12 2017.
[17] Gordon Plotkin. A structural approach to operational semantics. The Journal of Logic and Algebraic Programming, 60-61:17–139, 07 2004. doi:10.1016/j.jlap.2004.05.001.
[18] Arend Rensink and Heike Wehrheim. Weak sequential composition in process algebras. In Bengt Jonsson and Joachim Parrow, editors, 5th Conf. on Concurrency Theory (CONCUR), Lecture Notes in Computer Science, pages 226–241. Springer, 1994. doi:10.1007/BFb0015012.
[19] Harald Störrle. Semantics of interactions in uml 2.0. In IEEE Symposium on Human Centric Computing Languages and Environments, 2003. Proceedings. 2003, pages 129–136, 10 2003. doi:10.1109/HCC.2003.1260216.

Appendix A Proofs of section 3

Lemma (Lem.3.4).

For any $\diamond\in\{;,\leavevmode\nobreak\ ||\}$ , $T\in\mathcal{P}(\mathbb{T}_{\Omega})$ , $t$ in $\mathbb{T}_{\Omega}$ and $a\in\mathbb{A}_{\Omega}$ we have:

(a.t\in T^{\diamond*})\Rightarrow\left(\exists\leavevmode\nobreak\ t^{\prime}\in\mathbb{T}_{\Omega}\text{ s.t. }\left\{\begin{array}[]{l}(a.t^{\prime}\in T)\\ \wedge\leavevmode\nobreak\ (t\in(\{t^{\prime}\}\diamond T^{\diamond*}))\end{array}\right.\right)

Proof A.1.

By definition of the K-closure, $a.t\in T^{\diamond*}$ implies the existence of $j\geq 0$ s.t. $a.t\in T^{\diamond j}$ . We can then reason by induction on the power $j$ :

•

we cannot have $j=0$ because $T^{\diamond 0}=\{\epsilon\}$
•

if $j=1$ then $a.t\in T^{\diamond 1}=T$ and $t\in\{t\}\diamond\{\epsilon\}\subset\{t\}\diamond T^{\diamond*}$ therefore the property holds

•

if $j>1$ the fact that $a.t\in T^{\diamond j}=T\diamond T^{\diamond(j-1)}$ implies the existence of $t^{\prime\prime}\in T$ s.t. $a.t\in\{t^{\prime\prime}\}\diamond T^{\diamond(j-1)}$ then:

–
if $\diamond=;$ this implies that:
- *
  
  either $t^{\prime\prime}$ is of the form $a.t^{\prime}$ and $t\in\{t^{\prime}\};T^{;(j-1)}$ and therefore $t\in\{t^{\prime}\};T^{;*}$
- *
  
  or $t^{\prime\prime}=\epsilon$ and $a.t\in T^{;(j-1)}$ and we can use the induction hypothesis to conclude

–

if $\diamond=||$ this implies that:

*

either $t^{\prime\prime}$ is of the form $a.t^{\prime}$ and $t\in\{t^{\prime}\}||T^{||(j-1)}$ and therefore $t\in\{t^{\prime}\}||T^{||*}$

or there exists a certain $t^{\prime\prime\prime}$ s.t. we have $a.t^{\prime\prime\prime}\in T^{||(j-1)}$ and $t\in\{t^{\prime\prime}\}||\{t^{\prime\prime\prime}\}$ . Let us then remark that given that we have $a.t^{\prime\prime\prime}\in T^{||(j-1)}$ we can apply the induction hypothesis to reveal $t^{\prime}$ such that $a.t^{\prime}\in T$ and $t^{\prime\prime\prime}\in\{t^{\prime}\}||T^{||*}$ . We can then use the associativity and commutativity of $||$ as follows:

\begin{array}[]{lclr}t\in\{t^{\prime\prime}\}||(\{t^{\prime}\}||T^{||*})&\Rightarrow&t\in\{t^{\prime\prime}\}||(T^{||*}||\{t^{\prime}\})&\text{ commutativity}\\ &\Rightarrow&t\in(\{t^{\prime\prime}\}||T^{||*})||\{t^{\prime}\}&\text{ associativity}\\ &\Rightarrow&t\in T^{||*}||\{t^{\prime}\}&\text{ property of Kleene closure}\\ &\Rightarrow&t\in\{t^{\prime}\}||T^{||*}&\text{ commutativity}\end{array}

Lemma (Lem.3.6).

For any set of traces $T$ :

\begin{array}[]{ccc}T^{;^{\Lsh}*}=T^{;*}&\leavevmode\nobreak\ \leavevmode\nobreak\ \text{ and }\nobreak\leavevmode\nobreak\leavevmode&T^{||^{\Lsh}*}=T^{||*}\end{array}

Proof A.2.

Let us consider $\diamond\in\{;,\leavevmode\nobreak\ ||\}$ . By definition, we already have $T^{\diamond^{\Lsh}*}\subset T^{\diamond*}$ . To prove the other inclusion let us reason by induction on a member trace:

•

by definition $\epsilon\in T^{\diamond^{\Lsh}*}$ and $\epsilon\in T^{\diamond*}$
•
if the trace is of the form $a.t$ then if $a.t\in T^{\diamond*}$ , then, as per Lem.3.4 there exists a trace $t^{\prime}$ such that $a.t^{\prime}\in T$ and $t\in\{t^{\prime}\}\diamond T^{\diamond*}$ . This in turn implies that:
- –
  
  given that action $a$ is taken from $a.t^{\prime}$ , we have $a.t\in\{a.t^{\prime}\}\diamond^{\Lsh}T^{\diamond*}$
- –
  
  and there exists $t^{\prime\prime}\in T^{\diamond*}$ such that $t\in\{t^{\prime}\}\diamond\{t^{\prime\prime}\}$ . Given that $t^{\prime\prime}$ is strictly smaller than $a.t$ , we can apply the induction hypothesis to obtain that $t^{\prime\prime}\in T^{\diamond^{\Lsh}*}$ .
Therefore we have that $a.t\in\{a.t^{\prime}\}\diamond^{\Lsh}T^{\diamond^{\Lsh}*}$ , and hence $a.t\in T^{\diamond^{\Lsh}*}$

Appendix B Proofs of section 5

Lemma (Lem.5.2).

For any $i\in\mathbb{I}_{\Omega}$ we have $(i\downarrow)\Leftrightarrow(\epsilon\in\sigma_{d}(i))$

Proof B.1.

Let us reason by induction on the term structure of $i$ .

•

If $i=\varnothing$ the empty interaction, then we have both $\varnothing\downarrow$ and $\epsilon\in\sigma_{d}(\varnothing)$ .
•

If $i\in\mathbb{A}_{\Omega}$ , we have neither $i\downarrow$ nor $\epsilon\in\sigma_{d}(i)$ .
•
Let us now suppose that $i$ is of the form $strict(i_{1},i_{2})$ , with $i_{1}$ and $i_{2}$ two sub-interactions that satisfy the induction hypotheses $(i_{1}\downarrow)\Leftrightarrow(\epsilon\in\sigma_{d}(i_{1}))$ and $(i_{2}\downarrow)\Leftrightarrow(\epsilon\in\sigma_{d}(i_{2}))$ .
- $\Leftarrow$
  
  Let us suppose that $\epsilon\in\sigma_{d}(i)$ . By definition of $\sigma_{d}$ for the $strict$ constructor, this implies the existence of $t_{1}\in\sigma_{d}(i_{1})$ and $t_{2}\in\sigma_{d}(i_{2})$ such that $\epsilon\in(t_{1};t_{2})$ . This trivially implies that $t_{1}=\epsilon$ and $t_{2}=\epsilon$ . We can therefore apply the induction hypotheses, to obtain that $i_{1}\downarrow$ and $i_{2}\downarrow$ . This in turn means that $strict(i_{1},i_{2})\downarrow$ .
- $\Rightarrow$
  
  Reciprocally, if $strict(i_{1},i_{2})\downarrow$ , this means that both $i_{1}\downarrow$ and $i_{2}\downarrow$ . As per the induction hypotheses, this means that $\epsilon\in\sigma_{d}(i_{1})$ and $\epsilon\in\sigma_{d}(i_{2})$ . Therefore $\epsilon\in\sigma_{d}(i)$ .
•

For interactions of the form $par(i_{1},i_{2})$ and $seq(i_{1},i_{2})$ , the reasoning is the same as for the previous case.
•
If $i$ is of the form $alt(i_{1},i_{2})$ :
- $\Leftarrow$
  
  If $\epsilon\in\sigma_{d}(i)$ this means that either $\epsilon\in\sigma_{d}(i_{1})$ or $\epsilon\in\sigma_{d}(i_{2})$ or both. Let us suppose that it is in $\sigma_{d}(i_{1})$ (the other cases can be treated similarly). As per the induction hypothesis, we have $i_{1}\downarrow$ which implies that $alt(i_{1},i_{2})\downarrow$ .
- $\Rightarrow$
  
  Reciprocally, if $alt(i_{1},i_{2})\downarrow$ , then either $i_{1}\downarrow$ or $i_{2}\downarrow$ (or both). Let us suppose we have $i_{1}\downarrow$ . The induction hypothesis implies that $\epsilon\in\sigma_{d}(i_{1})$ and hence $\epsilon\in\sigma_{d}(i)$ .
•

If $i=loop_{k}(i_{1})$ , with $k\in\{X,H,S,P\}$ we always have $i\downarrow$ and $\epsilon\in\sigma_{d}(i)$ .

Lemma (Lem.5.5).

Proof B.2.

Given $l\in L$ , let us reason by induction on the term structure of $i$ .

•

If $i=\varnothing$ , then we have $\varnothing\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ and $\epsilon\in\sigma_{d}(\varnothing)$ satisfies $\neg(\epsilon\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ .
•
If $i=a\in\mathbb{A}_{\Omega}$ , we have:
- –
  
  $a\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ iff $\theta(a)\neq l$
- –
  
  and $\sigma_{d}(i)=\{a\}$ with trace $a$ verifying $\neg(a\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ iff $\theta(a)\neq l$
The two conditions are therefore equivalent.
•
Let us now suppose that $i$ is of the form $strict(i_{1},i_{2})$ , with $i_{1}$ and $i_{2}$ two sub-interactions that satisfy the induction hypotheses (we use the distributivity of $\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}$ over ;):
- $\Rightarrow$
  
  If $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ then both $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ and $i_{2}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ . We can therefore apply the induction hypotheses, which lets us consider two traces $t_{1}\in\sigma_{d}(i_{1})$ and $t_{2}\in\sigma_{d}(i_{2})$ such that $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ and $\neg(t_{2}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ . By definition of $\sigma_{d}$ , we have $(t_{1};t2)\subset\sigma_{d}(i)$ . This implies that $\exists\leavevmode\nobreak\ t\in(t_{1};t2)$ s.t. $\neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ and this trace is in $\sigma_{d}(i)$ .
- $\Leftarrow$
  
  Reciprocally, if $\exists\leavevmode\nobreak\ t\in\sigma_{d}(strict(i_{1},i_{2}))$ s.t. $\neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ , then, by definition of $\sigma_{d}$ , this means that there exist two traces $t_{1}\in\sigma_{d}(i_{1})$ and $t_{2}\in\sigma_{d}(i_{2})$ s.t. $t\in(t_{1};t_{2})$ . Then, we have $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ and $\neg(t_{2}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ . We can therefore apply the induction hypothesis which implies that $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ and $i_{2}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ , which, per the definition of $\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ , implies that $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ .
•

For interactions of the form $par(i_{1},i_{2})$ and $seq(i_{1},i_{2})$ , the reasoning is the same as for the previous case except that we reason on (respectively) the operators $||$ and $;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ over both of which the conflict $\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}$ is also distributive.
•
If $i=alt(i_{1},i_{2})$ :
- $\Rightarrow$
  
  If $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ then either or both $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ and $i_{2}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ . Let us suppose we have $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ (the other cases are similar). By the induction hypothesis, we have $\exists\leavevmode\nobreak\ t_{1}\in\sigma_{d}(i_{1})$ s.t. $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ . We then simply observe that $\sigma_{d}(i_{1})\subset\sigma_{d}(i)$ .
- $\Leftarrow$
  
  Reciprocally, if $\exists\leavevmode\nobreak\ t\in\sigma_{d}(alt(i_{1},i_{2}))$ s.t. $\neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ , this means that this trace $t$ must be found in either $\sigma_{d}(i_{1})$ or $\sigma_{d}(i_{2})$ . Let us suppose the first case (the other is similar). We can therefore apply the induction hypothesis which implies that $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ . Then, by the definition of $\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ , this implies that $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ .
•

Let us finally consider the case where $i$ is of the form $loop_{k}(i_{1})$ , with $k\in\{X,H,S,P\}$ . By definition, we always have $i\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ and the empty trace $\epsilon\in\sigma_{d}(i)$ verifies $\neg(\epsilon\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ .

Lemma (Lem.5.10).

For any $l\in L$ and any $i$ and $i^{\prime}$ from $\mathbb{I}_{\Omega}$ :

(i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i^{\prime})\Rightarrow(\sigma_{d}(i^{\prime})=\{t\in\sigma_{d}(i)\leavevmode\nobreak\ |\leavevmode\nobreak\ \neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)\})

Proof B.3.

Given $l\in L$ , let us reason by induction on the term structure of $i$ .

•

If $i=\varnothing$ then $\varnothing\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}\varnothing$ and $\sigma_{d}(\varnothing)=\{\epsilon\}$ . $\epsilon$ having no conflict w.r.t. $l$ , the property holds.
•

If $i=a\in\mathbb{A}_{\Omega}$ , the precondition $a\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ implies that $\theta(i)\neq l$ . Also, we have $a\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}a$ and $\sigma_{d}(a)=\{a\}$ has a single trace with no conflict w.r.t. $l$ . Hence the property holds.
•
Let us now suppose that $i$ is of the form $strict(i_{1},i_{2})$ , with $i_{1}$ and $i_{2}$ two sub-interactions that satisfy induction hypotheses i.e. such that, given $i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{1}^{\prime}$ and $i_{2}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{2}^{\prime}$ we have $\sigma_{d}(i_{1}^{\prime})=\{t_{1}\in\sigma_{d}(i_{1})\leavevmode\nobreak\ |\leavevmode\nobreak\ \neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)\}$ and $\sigma_{d}(i_{2}^{\prime})=\{t_{2}\in\sigma_{d}(i_{2})\leavevmode\nobreak\ |\leavevmode\nobreak\ \neg(t_{2}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)\}$ . Also, by definition of pruning, we have $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}strict(i_{1}^{\prime},i_{2}^{\prime})$ and let us denote it by $i^{\prime}=strict(i_{1}^{\prime},i_{2}^{\prime})$ for short.
- $\subset$
  
  If $t\in\sigma_{d}(i^{\prime})$ then there exist $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ and $t_{2}\in\sigma_{d}(i_{2}^{\prime})$ such that $t\in(t_{1};t_{2})$ . By the induction hypothesis, we have $t_{1}\in\sigma_{d}(i_{1})$ and $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b})l$ and $t_{2}\in\sigma_{d}(i_{2})$ and $\neg(t_{2}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b})l$ . Therefore $t\in\sigma_{d}(i_{1});\sigma_{d}(i_{2})=\sigma_{d}(i)$ , and $\neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ .
- $\supset$
  
  If $t\in\sigma_{d}(i)$ is s.t. $\neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ then this implies the existence of $t_{1}\in\sigma_{d}(i_{1})$ and $t_{2}\in\sigma_{d}(i_{2})$ s.t. $t\in(t_{1};t_{2})$ . The fact that $\neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ implies that both $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ and $\neg(t_{2}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)$ . According to the induction hypothesis, this means that $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ and $t_{2}\in\sigma_{d}(i_{2}^{\prime})$ . Therefore $(t_{1};t_{2})\subset\sigma_{d}(i^{\prime})$ and hence $t\in\sigma_{d}(i^{\prime})$ .
•

For interactions of the form $par(i_{1},i_{2})$ and $seq(i_{1},i_{2})$ , the reasoning is the same as for the previous case except that we reason on (respectively) the operators $||$ and $;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ over both of which the conflict $\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}$ is also distributive.

•

Let us now suppose that $i$ is of the form $loop_{k}(i_{1})$ with $k\in\{X,H,S,P\}$ and let us note $\diamond$ the corresponding operator on sets of traces, i.e. $\diamond=;$ if $k=X$ , $\diamond=;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}$ if $k=H$ , $\diamond=;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ if $k=S$ and $\diamond=||$ if $k=P$ . We then have:

–

if $i_{1}\not{\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}l$ , then $loop_{k}(i_{1})\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}\varnothing$ . As per the reciprocate of Lem.5.5, if $i_{1}$ does not avoid $l$ , this means that all the traces from $\sigma_{d}(i_{1})$ have conflicts with $l$ . This means that all the traces obtained from merging traces from $i_{1}$ have conflicts with $l$ . Therefore the empty trace $\epsilon$ is the only trace from $\sigma_{d}(loop_{k}(i_{1}))$ which has no conflict with $l$ . Given that $\sigma_{d}(\varnothing)=\{\epsilon\}$ , the property holds.

–

if $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}l$ , then there exists a unique $i_{1}^{\prime}$ such that $i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{l}i_{1}^{\prime}$ and we suppose the induction hypothesis $\sigma_{d}(i_{1}^{\prime})=\{t_{1}\in\sigma_{d}(i_{1})\leavevmode\nobreak\ |\leavevmode\nobreak\ \neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)\}$ . Then we have:

\begin{array}[]{lcl}\sigma_{d}(loop_{k}(i_{1}^{\prime}))&=&\sigma_{d}(i_{1}^{\prime})^{\diamond*}\\ &=&\{t\in\sigma_{d}(i_{1})\leavevmode\nobreak\ |\leavevmode\nobreak\ \neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)\}^{\diamond*}\\ &=&\{t\in\sigma_{d}(i_{1})^{\diamond*}\leavevmode\nobreak\ |\leavevmode\nobreak\ \neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)\}\\ &=&\{t\in\sigma_{d}(loop_{k}(i_{1})))\leavevmode\nobreak\ |\leavevmode\nobreak\ \neg(t\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}l)\}\end{array}

Indeed, the conflict $\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}$ distributes over $\diamond$ and hence any trace obtained from merging traces from $i_{1}$ has no conflict w.r.t. $l$ iff it is obtained from merging traces from $i_{1}$ that all have no conflict with $l$ . Therefore, traces that have no conflict w.r.t. $l$ are exactly those that are obtained from merging traces with no conflicts w.r.t. $l$ . Those traces are those from $loop_{k}(i_{1}^{\prime})$ as per the induction hypothesis. Therefore the property holds.

Appendix C Proofs of section 6

Lemma (Lem.6.1).

For any $a\in\mathbb{A}_{\Omega}$ , $t\in\mathbb{T}_{\Omega}$ and $i$ and $i^{\prime}$ from $\mathbb{I}_{\Omega}$ :

\left(\begin{array}[]{c}(i\xrightarrow{a}i^{\prime})\wedge(t\in\sigma_{d}(i^{\prime}))\end{array}\right)\Rightarrow(a.t\in\sigma_{d}(i))

Proof C.1.

Given $i$ and $i^{\prime}$ in $\mathbb{I}_{\Omega}$ , $a$ in $\mathbb{A}_{\Omega}$ and $t\in\mathbb{T}_{\Omega}$ , let us suppose that $i\xrightarrow{a}i^{\prime}$ and that $t\in\sigma_{d}(i^{\prime})$ . In order to prove $a.t\in\sigma_{d}(i)$ let us reason by induction on the cases that makes the hypothesis $i\xrightarrow{a}i^{\prime}$ possible. There are 13 such cases, as per the 13 rules from Def.5.12:

1.

when executing an atomic action, we have $i\in\mathbb{A}_{\Omega}$ and $i^{\prime}=\varnothing$ . Then $\sigma_{d}(i)=\{i\}$ and $\sigma_{d}(\varnothing)=\{\epsilon\}$ . The property $i.\epsilon=i\in\sigma_{d}(i)$ holds.
2.

when executing an action on the left of an alternative, we have $i$ of the form $alt(i_{1},i_{2})$ , and $i^{\prime}=i_{1}^{\prime}$ such that $i_{1}\xrightarrow{a}i_{1}^{\prime}$ . As a result, $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t\in\sigma_{d}(i_{1}^{\prime})$ . We can therefore apply the induction hypothesis on sub-interaction $i_{1}$ to obtain that $a.t\in\sigma_{d}(i_{1})$ . Given that $\sigma_{d}(i_{1})\subset\sigma_{d}(i)$ , the property holds.
3.

the case for executing an action on the right of an alternative can be treated similarly
4.

when executing an action on the left of a $par$ , we have $i$ of the form $par(i_{1},i_{2})$ , and $i^{\prime}=par(i_{1}^{\prime},i_{2})$ such that $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t\in\sigma_{d}(par(i_{1}^{\prime},i_{2}))$ . By definition of $\sigma_{d}$ , we have that there exist $(t_{1}^{\prime},t_{2})\in\sigma_{d}(i_{1}^{\prime})\times\sigma_{d}(i_{2})$ s.t. $t\in(t_{1}^{\prime}||t_{2})$ . Therefore we have $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t_{1}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ . Hence we can apply the induction hypothesis on sub-interaction $i_{1}$ to obtain that $a.t_{1}^{\prime}\in\sigma_{d}(i_{1})$ . Given that $\sigma_{d}(par(i_{1},i_{2}))$ is the union of all the $(t_{\alpha}||t_{\beta})$ with $t_{\alpha}$ and $t_{\beta}$ traces from $i_{1}$ and $i_{2}$ , we have that $(a.t_{1}^{\prime}||t_{2})\subset\sigma_{d}(i)$ . In particular, we know that $t\in(t_{1}^{\prime}||t_{2})$ , so, by definition of the $||$ operator, we have that $a.t\in(a.t_{1}^{\prime}||t_{2})$ . Therefore the property holds.
5.

the case for executing an action on the right of a $par$ can be treated similarly
6.

executing an action on the left of a $strict$ can be treated like 4.
7.

when executing an action on the right of a $strict$ , we have $i$ of the form $strict(i_{1},i_{2})$ , and $i^{\prime}=i_{2}^{\prime}$ such that $i_{2}\xrightarrow{a}i_{2}^{\prime}$ with the added hypothesis that $i_{1}\downarrow$ . Given that $t\in\sigma_{d}(i_{2}^{\prime})$ and $i_{2}\xrightarrow{a}i_{2}^{\prime}$ , we can apply the induction hypothesis on sub-interaction $i_{2}$ to obtain that $a.t\in\sigma_{d}(i_{2})$ . Given that $\sigma_{d}(strict(i_{1},i_{2}))$ includes $\sigma_{d}(i_{2})$ when $i_{1}\downarrow$ , and given that we know $i_{1}\downarrow$ to be true, the property holds.
8.

executing an action on the left of a $seq$ can be treated like 4.
9.
when executing an action on the right of a $seq$ , we have $i$ of the form $seq(i_{1},i_{2})$ , and $i^{\prime}=seq(i_{1}^{\prime},i_{2}^{\prime})$ such that $i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i_{1}^{\prime}$ and $i_{2}\xrightarrow{a}i_{2}^{\prime}$ with the added hypothesis that $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\theta(a)$ implied by the fact that $i_{1}$ prunes into $i_{1}^{\prime}$ . Given that $t\in\sigma_{d}(i^{\prime})$ , there exists $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ and $t_{2}\in\sigma_{d}(i_{2}^{\prime})$ s.t. $t\in(t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2})$ . We then remark that:
- •
  
  $i_{2}\xrightarrow{a}i_{2}^{\prime}$ and $t_{2}\in\sigma_{d}(i_{2}^{\prime})$ . Hence we can apply the induction hypothesis on sub-interaction $i_{2}$ to obtain that $a.t_{2}\in\sigma_{d}(i_{2})$ .
- •
  
  the fact that $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ implies, as per Lem.5.10 that $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ . As a result, by definition of the weak sequencing operator, $(t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}a.t_{2})$ includes $a.t$ .
Finally, given that $\sigma_{d}(i)$ includes all $(t_{\alpha};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{\beta})$ s.t. $t_{\alpha}\in\sigma_{d}(i_{1})$ and $t_{\beta}\in\sigma_{d}(i_{2})$ , we have, in particular $(t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}a.t_{2})\subset\sigma_{d}(i)$ . Hence the property holds.
10.
when executing an action underneath a $loop_{X}$ , we have $i$ of the form $loop_{X}(i_{1})$ and $i^{\prime}=strict(i_{1}^{\prime},loop_{X}(i_{1}))$ such that $i_{1}\xrightarrow{a}i_{1}^{\prime}$ . We have that $t\in\sigma_{d}(i^{\prime})$ . Therefore there exists $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ and $t_{2}\in\sigma_{d}(i)$ s.t. $t\in(t_{1};t_{2})$ . We then remark that:
- •
  
  $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ . Hence we can apply the induction hypothesis on sub-interaction $i_{1}$ , which implies that $a.t_{1}\in\sigma_{d}(i_{1})$ .
- •
  
  and as a result, given that $t_{2}\in\sigma_{d}(loop_{X}(i_{1}))=\sigma_{d}(i_{1})^{;*}$ , and $a.t_{1}\in\sigma_{d}(i_{1})$ , we have, $(a.t_{1};t_{2})\subset\sigma_{d}(i_{1})^{;*}$ i.e. $(a.t_{1};t_{2})\subset\sigma_{d}(i)$
Then, given that $t\in(t_{1};t_{2})$ , we have immediately that $a.t\in(a.t_{1};t_{2})$ because it is always possible to add actions from the left. Therefore $a.t\in\sigma_{d}(i)$ , so the property holds.
11.

executing an action underneath a $loop_{H}$ can be treated like 10.
12.
when executing an action underneath a $loop_{S}$ , we have $i$ of the form $loop_{S}(i_{1})$ and $i^{\prime}=seq(i_{0}^{\prime},seq(i_{1}^{\prime},loop_{S}(i_{1})))$ such that $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i_{0}^{\prime}$ . Given that $t\in\sigma_{d}(i^{\prime})$ , there exists $t_{0}\in\sigma_{d}(i_{0}^{\prime})$ , $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ and $t_{2}\in\sigma_{d}(i)$ s.t. $t\in(t_{0};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2})$ . We then remark that:
- •
  Given that $i\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i_{0}^{\prime}$ we have that:
  - –
    
    $\sigma_{d}(i_{0}^{\prime})\subset\sigma_{d}(i)$ and, given that $\sigma_{d}(i)=\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}$ , is a weak Kleene closure we have that $\sigma_{d}(i);_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i)\subset\sigma_{d}(i)$ and therefore $\sigma_{d}(i_{0}^{\prime});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i)\subset\sigma_{d}(i)$
  - –
    
    and, given that $t_{0}\in\sigma_{d}(i_{0}^{\prime})$ , we have as per Lem.5.10 that $\neg(t_{0}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ . Therefore, for any $t_{\beta}$ and any $t_{\alpha}\in(t_{0};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{\beta})$ we have $a.t_{\alpha}\in(t_{0};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}a.t_{\beta})$ given that we can take action $a$ , which have no conflict w.r.t $t_{0}$ , on the right side
- •
  
  We have $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ . Hence we can apply the induction hypothesis on sub-interaction $i_{1}$ , which implies that $a.t_{1}\in\sigma_{d}(i_{1})$
- •
  
  Given that $t_{2}\in\sigma_{d}(loop_{S}(i_{1}))=\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}$ , and $a.t_{1}\in\sigma_{d}(i_{1})$ , we have, $(a.t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2})\subset\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}$ i.e. $(a.t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2})\subset\sigma_{d}(i)$
Finally, given $a.t\in(t_{0};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}a.t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2})\subset(\sigma_{d}(i_{0}^{\prime});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i))\subset\sigma_{d}(i)$ , the property holds.
13.

executing an action underneath a $loop_{P}$ can be treated like 10.

Theorem (Th.6.3).

For any $i\in\mathbb{I}_{\Omega}$ we have $\sigma_{o}(i)\subset\sigma_{d}(i)$

Proof C.2.

Let us consider $i\in\mathbb{I}_{\Omega}$ and $t\in\sigma_{o}(i)$ and let us reason by induction on the trace $t$ .

•

If $t=\epsilon$ , then, as per the definition of $\sigma_{o}$ , this means that $i\downarrow$ . Then as per Lem.5.2, this means that $\epsilon\in\sigma_{d}(i)$ .
•

If $t=a.t^{\prime}$ then, by definition of $\sigma_{o}$ , $a.t^{\prime}\in\sigma_{o}(i)$ iff $\exists\leavevmode\nobreak\ i^{\prime}\in\mathbb{I}_{\Omega}$ s.t. $i\xrightarrow{a}i^{\prime}$ and $t^{\prime}\in\sigma_{o}(i^{\prime})$ . Let us therefore consider such an interaction $i^{\prime}$ . By the induction hypothesis on trace $t^{\prime}$ , we have $(t^{\prime}\in\sigma_{o}(i^{\prime}))\Rightarrow(t^{\prime}\in\sigma_{d}(i^{\prime}))$ . As a result we have $i\xrightarrow{a}i^{\prime}$ and $t^{\prime}\in\sigma_{d}(i^{\prime})$ . We can therefore apply Lem.6.1 to conclude that $a.t^{\prime}\in\sigma_{d}(i)$ . Hence the property holds.

Lemma C.3 (Lem.6.5).

For any $a\in\mathbb{A}_{\Omega}$ , $t\in\mathbb{T}_{\Omega}$ and $i\in\mathbb{I}_{\Omega}$ :

(a.t\in\sigma_{d}(i))\Rightarrow\left(\exists\leavevmode\nobreak\ i^{\prime}\in\mathbb{I}_{\Omega},\leavevmode\nobreak\ \begin{array}[]{c}(i\xrightarrow{a}i^{\prime})\wedge(t\in\sigma_{d}(i^{\prime}))\end{array}\right)

Proof C.4.

Let us consider $i\in\mathbb{I}_{\Omega}$ , $a\in\mathbb{A}_{\Omega}$ and $t\in\mathbb{T}_{\Omega}$ . Let us suppose that $a.t\in\sigma_{d}(i)$ and let us reason by induction on the term structure of $i$ .

•

we cannot have $i=\varnothing$ because it contradicts $a.t\in\sigma_{d}(i)$
•

if $i\in\mathbb{A}_{\Omega}$ then $a.t\in\sigma_{d}(i)$ implies that $i=a$ and $t=\epsilon$ . We then have the existence of $i^{\prime}=\varnothing$ which indeed satisfies that $a\xrightarrow{a}\varnothing$ and $\epsilon\in\sigma_{d}(\varnothing)$
•

if $i$ is of the form $alt(i_{1},i_{2})$ then $a.t\in\sigma_{d}(i)$ implies either $a.t\in\sigma_{d}(i_{1})$ or $a.t\in\sigma_{d}(i_{2})$ . Let us suppose it is the first case (the second is identical). Then, we can apply the induction hypothesis on sub-interaction $i_{1}$ , which reveals the existence of $i_{1}^{\prime}$ such that $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t\in\sigma_{d}(i_{1}^{\prime})$ . By definition of the execution relation " $\rightarrow$ ", this implies that $alt(i_{1},i_{2})\xrightarrow{a}i_{1}^{\prime}$ . As a result, we have identified $i^{\prime}=i_{1}^{\prime}$ which satisfies the property.
•
if $i$ is of the form $par(i_{1},i_{2})$ then $a.t\in\sigma_{d}(i)$ implies the existence of traces $t_{1}$ and $t_{2}$ such that $t_{1}\in\sigma_{d}(i_{1})$ and $t_{2}\in\sigma_{d}(i_{2})$ and $a.t\in(t_{1}||t_{2})$ . This then implies:
- –
  
  either that $t_{1}$ is of the form $a.t_{1}^{\prime}$ and $t\in(t_{1}^{\prime}||t_{2})$
- –
  
  or $t_{2}$ is of the form $a.t_{2}^{\prime}$ and $t\in(t_{1}||t_{2}^{\prime})$
As both case can be treated identically, let us suppose it is the first case. Given that we have $a.t_{1}^{\prime}\in\sigma_{d}(i_{1})$ , we can apply the induction hypothesis on sub-interaction $i_{1}$ , which reveals the existence of $i_{1}^{\prime}$ such that $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t_{1}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ . By definition of the execution relation " $\rightarrow$ ", this implies that $par(i_{1},i_{2})\xrightarrow{a}par(i_{1}^{\prime},i_{2})$ . By definition of $\sigma_{d}$ , given that $t_{1}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ and $t_{2}\in\sigma_{d}(i_{2})$ , we have $(t_{1}^{\prime}||t_{2})\subset\sigma_{d}(par(i_{1}^{\prime},i_{2}))$ . Then, given that $t\in(t_{1}^{\prime}||t_{2})$ , this implies that $t\in\sigma_{d}(par(i_{1}^{\prime},i_{2}))$ . We therefore have identified $i^{\prime}=par(i_{1}^{\prime},i_{2})$ which satisfies the property.
•
if $i$ is of the form $strict(i_{1},i_{2})$ then $a.t\in\sigma_{d}(i)$ implies the existence of traces $t_{1}$ and $t_{2}$ such that $t_{1}\in\sigma_{d}(i_{1})$ and $t_{2}\in\sigma_{d}(i_{2})$ and $a.t\in(t_{1};t_{2})$ . This then implies:
- –
  
  either that $t_{1}$ is of the form $a.t_{1}^{\prime}$ and $t\in(t_{1}^{\prime};t_{2})$ . In that case we can apply the induction hypothesis on sub-interaction $i_{1}$ , which reveals the existence of $i_{1}^{\prime}$ s.t. $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t_{1}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ . By definition of the execution relation " $\rightarrow$ ", this implies that $strict(i_{1},i_{2})\xrightarrow{a}strict(i_{1}^{\prime},i_{2})$ . By definition of $\sigma_{d}$ , given that $t_{1}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ and $t_{2}\in\sigma_{d}(i_{2})$ , we have $(t_{1}^{\prime};t_{2})\subset\sigma_{d}(strict(i_{1}^{\prime},i_{2}))$ . Then, given that $t\in(t_{1}^{\prime};t_{2})$ this implies that $t\in\sigma_{d}(strict(i_{1}^{\prime},i_{2}))$ . Hence $i^{\prime}=strict(i_{1}^{\prime},i_{2})$ satisfies the property.
- –
  
  or that $t_{1}=\epsilon$ and $t_{2}=a.t$ . On the one hand, the fact that $t_{1}=\epsilon\in\sigma_{d}(i_{1})$ implies, as per Lem.5.2, that $i_{1}\downarrow$ . On the other hand, with $t_{2}=a.t\in\sigma_{d}(i_{2})$ , we can apply the induction hypothesis on sub-interaction $i_{2}$ , which reveals the existence of $i_{2}^{\prime}$ s.t. $i_{2}\xrightarrow{a}i_{2}^{\prime}$ and $t\in\sigma_{d}(i_{2}^{\prime})$ . By definition of the execution relation " $\rightarrow$ ", and because the precondition $i_{1}\downarrow$ is verified, this implies that $strict(i_{1},i_{2})\xrightarrow{a}i_{2}^{\prime}$ . As a result, we have identified $i^{\prime}=i_{2}^{\prime}$ which satisfies the property.
•
if $i$ is of the form $seq(i_{1},i_{2})$ then $a.t\in\sigma_{d}(i)$ implies the existence of traces $t_{1}$ and $t_{2}$ such that $t_{1}\in\sigma_{d}(i_{1})$ and $t_{2}\in\sigma_{d}(i_{2})$ and $a.t\in(t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2})$ . This then implies:
- –
  
  either that $t_{1}=a.t_{1}^{\prime}$ and $t\in(t_{1}^{\prime};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2})$ . In that case we can apply the induction hypothesis on sub-interaction $i_{1}$ , which reveals the existence of $i_{1}^{\prime}$ s.t. $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t_{1}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ . By definition of the execution relation " $\rightarrow$ ", this implies that $seq(i_{1},i_{2})\xrightarrow{a}seq(i_{1}^{\prime},i_{2})$ . By definition of $\sigma_{d}$ , given that $t_{1}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ and $t_{2}\in\sigma_{d}(i_{2})$ , we have $(t_{1}^{\prime};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2})\subset\sigma_{d}(seq(i_{1}^{\prime},i_{2}))$ . Then, given that $t\in(t_{1}^{\prime};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2})$ , this implies that $t\in\sigma_{d}(seq(i_{1}^{\prime},i_{2}))$ . We therefore have identified $i^{\prime}=seq(i_{1}^{\prime},i_{2})$ which satisfies the property.
- –
  
  or that $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ and that $t_{2}$ is of the form $a.t_{2}^{\prime}$ with $t\in(t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2}^{\prime})$ . On the one hand, the fact that $t_{1}\in\sigma_{d}(i_{1})$ is such that $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ , ensures, as per Lem.5.5, that $i_{1}\downarrow^{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\theta(a)$ and therefore, as per Lem.5.8, that there exists a unique $i_{1}^{\prime}$ such that $i_{1}\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i_{1}^{\prime}$ . On the other hand, with $t_{2}=a.t_{2}^{\prime}\in\sigma_{d}(i_{2})$ , we can apply the induction hypothesis on sub-interaction $i_{2}$ , which reveals the existence of $i_{2}^{\prime}$ s.t. $i_{2}\xrightarrow{a}i_{2}^{\prime}$ and $t_{2}^{\prime}\in\sigma_{d}(i_{2}^{\prime})$ . By definition of the execution relation " $\rightarrow$ ", this implies that $seq(i_{1},i_{2})\xrightarrow{a}seq(i_{1}^{\prime},i_{2}^{\prime})$ . Given that $t_{1}\in\sigma_{d}(i_{1})$ is such that $\neg(t_{1}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ , as per Lem.5.10, this implies that $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ . By definition of $\sigma_{d}$ , given that $t_{1}\in\sigma_{d}(i_{1}^{\prime})$ and $t_{2}^{\prime}\in\sigma_{d}(i_{2}^{\prime})$ , we have $(t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2}^{\prime})\subset\sigma_{d}(seq(i_{1}^{\prime},i_{2}^{\prime}))$ . Then, given that $t\in(t_{1};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}t_{2}^{\prime})$ , this implies that $t\in\sigma_{d}(seq(i_{1}^{\prime},i_{2}^{\prime}))$ . We therefore have identified $i^{\prime}=seq(i_{1}^{\prime},i_{2}^{\prime})$ which satisfies the property.
•

if $i$ is of the form $loop_{X}(i_{1})$ then $a.t\in\sigma_{d}(i)$ means that $a.t\in\sigma_{d}(i_{1})^{;*}$ and hence, as per Lem.3.4, this implies the existence of a trace $t^{\prime}$ such that $a.t^{\prime}\in\sigma_{d}(i_{1})$ and $t\in\{t^{\prime}\};\sigma_{d}(i_{1})^{;*}$ . Then, the fact that $a.t^{\prime}\in\sigma_{d}(i_{1})$ allows us to apply the induction hypothesis on sub-interaction $i_{1}$ to reveal the existence of $i_{1}^{\prime}$ such that $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ . By definition of the execution relation " $\rightarrow$ ", this implies that $loop_{X}(i_{1})\xrightarrow{a}strict(i_{1}^{\prime},loop_{X}(i_{1}))$ . By definition of $\sigma_{d}$ , given that $t^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ and that $t\in\{t^{\prime}\};\sigma_{d}(i_{1})^{;*}$ , we have that $t\in\sigma_{d}(strict(i_{1}^{\prime},loop_{X}(i_{1})))$ . Hence $i^{\prime}=strict(i_{1}^{\prime},loop_{X}(i_{1}))$ satisfies the property.
•

for $i$ is of the form $loop_{P}(i_{1})$ the proof can be handled as in the previous case
•

if $i$ is of the form $loop_{H}(i_{1})$ then $a.t\in\sigma_{d}(i)$ means that $a.t\in\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ . By definition, there exists $j>0$ such that $a.t\in\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}j}=\sigma_{d}(i_{1});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}(j-1)}\subset\sigma_{d}(i_{1});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ . Because the restricted operator $;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}$ only allows to take the first action of recomposed traces from the left hand side, we can identify a trace $t^{\prime}$ s.t. $a.t^{\prime}\in\sigma_{d}(i_{1})$ and $t\in\{t^{\prime}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ . Hence, we can apply the induction hypothesis on sub-interaction $i_{1}$ to reveal the existence of $i_{1}^{\prime}$ such that $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ . By definition of the execution relation " $\rightarrow$ ", this implies that $loop_{H}(i_{1})\xrightarrow{a}seq(i_{1}^{\prime},loop_{H}(i_{1}))$ . By definition of $\sigma_{d}$ , given that $t^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ and that $t\in\{t^{\prime}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}^{\Lsh}*}$ , we have that $t\in\sigma_{d}(seq(i_{1}^{\prime},loop_{H}(i_{1})))$ . We therefore have identified $i^{\prime}=seq(i_{1}^{\prime},loop_{H}(i_{1}))$ which satisfies the property.
•
if $i$ is of the form $loop_{S}(i_{1})$ then $a.t\in\sigma_{d}(i)$ means that $a.t\in\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}*}$ . By definition there exists $n>0$ such that $a.t\in\sigma_{d}(i_{1})^{;_{\scalerel*{\leavevmode{\ooalign{\raisebox{3.47221pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}n}$ . As a result, we can identify traces $t_{1}$ through $t_{n}$ such that for any $j\in[1,n]$ , $t_{j}\in\sigma_{d}(i_{1})$ and $a.t\in\{t_{1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{n}\}$ . By definition of the weak sequencing operator, action $a$ is taken from a certain $t_{j}$ with $j\in[1,n]$ which is therefore of the form $t_{j}=a.t_{j}^{\prime}$ and we have, for any $k<j$ , $\neg(t_{k}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ (otherwise we could not take $a$ from $t_{j}$ ) and $t\in\{t_{1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j-1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j}^{\prime}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j+1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{n}\}$ . We can then remark the following:
- –
  considering $i_{0}^{\prime}$ such that $loop_{S}(i_{1})\mathrlap{\raisebox{-0.125pt}{\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}}\xrightarrow{\theta(a)}i_{0}^{\prime}$ (which existence is guaranteed by Lem.5.8 given that a loop always evades any lifeline), because, for any $k<j$ , we have $\neg(t_{k}\scalerel*{\leavevmode{\ooalign{\raisebox{6.94444pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}\theta(a))$ then, as per Lem.5.10, for all $k<j$ , we have $t_{k}\in\sigma_{d}(i_{0}^{\prime})$ . Then:
  - *
    
    If all the $t_{k}$ are the empty trace then $\{t_{1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j-1}\}=\{\epsilon\}\subset\sigma_{d}(i_{0}^{\prime})$ ( $\sigma_{d}(i_{0}^{\prime})$ contains at least $\epsilon$ because $loop_{S}(i_{1})$ does)
  - *
    
    If at least one $t_{k}$ is not the empty trace then $i_{0}^{\prime}$ is a non empty $loop_{S}$ , and, because it is a $loop_{S}$ , given that for all $k<j$ , we have $t_{k}\in\sigma_{d}(i_{0}^{\prime})$ then $\{t_{1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j-1}\}\subset\sigma_{d}(i_{0}^{\prime})$ (because a $loop_{S}$ is closed under repetition by $;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}$ )
  Hence $\{t_{1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j-1}\}\subset\sigma_{d}(i_{0}^{\prime})$ and therefore $t\in\sigma_{d}(i_{0}^{\prime});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j}^{\prime}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j+1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{n}\}$
- –
  
  given that, for any $k>j$ we have that $t_{k}\in\sigma_{d}(i)$ and because $i$ is a loop ( $i=loop_{S}(i_{1})$ ), then $\{t_{j+1}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\cdots;_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{n}\}\subset\sigma_{d}(i)$ and therefore $t\in\sigma_{d}(i_{0}^{\prime});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j}^{\prime}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i)$
- –
  
  given that $t_{j}=a.t_{j}^{\prime}\in\sigma_{d}(i_{1})$ we can apply the induction hypothesis on sub-interaction $i_{1}$ to reveal the existence of $i_{1}^{\prime}$ such that $i_{1}\xrightarrow{a}i_{1}^{\prime}$ and $t_{j}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ . By definition of the execution relation " $\rightarrow$ ", this implies that $loop_{S}(i_{1})\xrightarrow{a}seq(i_{0}^{\prime},seq(i_{1}^{\prime},loop_{S}(i_{1})))$
- –
  
  finally, given that we have shown that $t\in\sigma_{d}(i_{0}^{\prime});_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\{t_{j}^{\prime}\};_{\scalerel*{\leavevmode{\ooalign{\raisebox{4.8611pt}{$\times$}\cr\raisebox{0.0pt}{\scalebox{1.0}[-1.0]{$\times$}}\cr}}}{b}}\sigma_{d}(i)$ and because $t_{j}^{\prime}\in\sigma_{d}(i_{1}^{\prime})$ , by definition of $\sigma_{d}$ we can conclude that $t\in\sigma_{d}(seq(i_{0}^{\prime},seq(i_{1}^{\prime},loop_{S}(i_{1}))))$ . Therefore we have identified $i^{\prime}=seq(i_{0}^{\prime},seq(i_{1}^{\prime},loop_{S}(i_{1})))$ which satisfies the property.

Theorem (Th.6.7).

For any $i\in\mathbb{I}_{\Omega}$ we have $\sigma_{o}(i)\supset\sigma_{d}(i)$

Proof C.5.

Let us consider $i\in\mathbb{I}_{\Omega}$ and $t\in\sigma_{d}(i)$ and let us reason by induction on the trace $t$ .

•

If $t=\epsilon$ , the fact that $t=\epsilon\in\sigma_{d}(i)$ implies, as per Lem.5.2, that $i\downarrow$ . Then, by definition of $\sigma_{o}$ , this means that $\epsilon\in\sigma_{o}(i)$ .
•

If $t=a.t^{\prime}$ then, the fact that $a.t^{\prime}\in\sigma_{d}(i)$ implies, as per Lem.6.5, that there exists an interaction $i^{\prime}$ such that $i\xrightarrow{a}i^{\prime}$ and $t^{\prime}\in\sigma_{d}(i^{\prime})$ . Let us therefore consider such an interaction $i^{\prime}$ . By the induction hypothesis on trace $t^{\prime}$ , we have $(t^{\prime}\in\sigma_{d}(i^{\prime}))\Rightarrow(t^{\prime}\in\sigma_{o}(i^{\prime}))$ . As a result we have $i\xrightarrow{a}i^{\prime}$ and $t^{\prime}\in\sigma_{o}(i^{\prime})$ . By definition of the operational semantics, this implies that $a.t^{\prime}\in\sigma_{o}(i)$ . Hence the property holds.


before pruning	pruning w.r.t ${\color[rgb]{0.0859375,0.0859375,0.51171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.0859375,0.0859375,0.51171875}l_{3}}$	after pruning

A structural operational semantics for interactions with a look at loops

Abstract

keywords:

category:

1 Introduction

2 Basic interactions & intuition of their meaning

2.1 Preliminaries

2.2 Basic interactions

3 Repetition operators in the semantic domain

Definition 3.1 (Kleene closures).

Definition 3.2 (Restricted scheduling operators).

Definition 3.3 (Head-first closures).

Lemma 3.4.

Proof 3.5.

Lemma 3.6 (Equivalence of HF & K closures for ; & ||||).

Proof 3.7.

4 Syntax & denotational semantics

Definition 4.1 (Interaction Language).

Definition 4.2 (Denotational semantics).

5 A structural operational semantics

5.1 Termination

Definition 5.1 (Termination).

Lemma 5.2 (Termination w.r.t. σd\sigma_{d}).

Proof 5.3.

5.2 Dealing with weak-sequencing using evasion & pruning

Definition 5.4 (Evasion).

Lemma 5.5 (Evasion w.r.t. σd\sigma_{d}).

Proof 5.6.

Definition 5.7 (Pruning).

Lemma 5.8 (Conditional existence & unicity for pruning).

Proof 5.9.

Lemma 5.10 (Pruning w.r.t. σd\sigma_{d}).

Proof 5.11.

5.3 Execution relation & operational semantics

Definition 5.12 (Execution relation).

Definition 5.13 (Operational semantics).

5.4 Illustrative example

6 Proving the equivalence of both semantics

Lemma 6.1 (Property 1 of →\rightarrow w.r.t. σd\sigma_{d}).

Proof 6.2.

Theorem 6.3 (Inclusion of σo\sigma_{o} in σd\sigma_{d}).

Proof 6.4.

Lemma 6.5 (Property 2 of →\rightarrow w.r.t. σd\sigma_{d}).

Proof 6.6.

Theorem 6.7 (Inclusion of σd\sigma_{d} in σo\sigma_{o}).

Proof 6.8.

7 Related works

8 Conclusion & further work

References

Appendix A Proofs of section 3

Lemma (Lem.3.4).

Proof A.1.

Lemma (Lem.3.6).

Proof A.2.

Appendix B Proofs of section 5

Lemma (Lem.5.2).

Proof B.1.

Lemma (Lem.5.5).

Proof B.2.

Lemma (Lem.5.10).

Proof B.3.

Appendix C Proofs of section 6

Lemma (Lem.6.1).

Proof C.1.

Theorem (Th.6.3).

Proof C.2.

Lemma C.3 (Lem.6.5).

Proof C.4.

Theorem (Th.6.7).

Proof C.5.

Lemma 3.6 (Equivalence of HF & K closures for ; & $||$ ).

Lemma 5.2 (Termination w.r.t. $\sigma_{d}$ ).

Lemma 5.5 (Evasion w.r.t. $\sigma_{d}$ ).

Lemma 5.10 (Pruning w.r.t. $\sigma_{d}$ ).

Lemma 6.1 (Property 1 of $\rightarrow$ w.r.t. $\sigma_{d}$ ).

Theorem 6.3 (Inclusion of $\sigma_{o}$ in $\sigma_{d}$ ).

Lemma 6.5 (Property 2 of $\rightarrow$ w.r.t. $\sigma_{d}$ ).

Theorem 6.7 (Inclusion of $\sigma_{d}$ in $\sigma_{o}$ ).