## 2 Event Language
### Trace Semantics of Expressions
: Consider the trace system \(TS_{0}=((A_{0},D_{0}),T_{0})\), with:  
\(A_{0}=\{a\}\), \(D_{0}=\{(a,a)\}\) and \(T_{0}=\{[a]\}\)  
\[(TS_{0})^{*}=((\{a\}\cup\{\lfloor\ \rfloor_{T_{0}}\},\{(a,a),(\lfloor\ \rfloor_{T_{0}},\lfloor\ \rfloor_{T_{0}}),(a,\lfloor\ \rfloor_{T_{0}}),(\lfloor\ \rfloor_{T_{0}},a)\}),\{[\epsilon],\lfloor\ \rfloor_{T_{0}}\})\]The actual traces of \((TS_{0})^{*}\) are all of the partial traces that can be obtained by filling its hole by means of the traces of \(T_{0}\): some examples are \([a\ |\ ]_{T_{0}}],[aa\ |\ ]_{T_{0}}],[aaa\ |\ ]_{T_{0}}]; Definition 1 will show the formal way in which more complete traces can be obtained. Other operations on trace systems are the following ones. * Let \(TS_{1}=(\Sigma_{1},T_{1})\) and \(TS_{2}=(\Sigma_{2},T_{2})\), with \(\Sigma_{1}=(A_{1},D_{1})\) and \(\Sigma_{2}=(A_{2},D_{2})\), be two trace systems. * Their concatenation is the system: \[TS_{1}.TS_{2}=(\Sigma^{\prime},T^{\prime})\] \[\text{where: }\ \Sigma^{\prime}=(A_{1}\cup A_{2},D_{1}D_{2}^{\circ}), \text{ and }T^{\prime}=\{\tau_{1}\tau_{2}\ |\ \tau_{1}\in T_{1},\ \tau_{2}\in T_{2}\}\]
* their nondeterministic composition is the system: \[TS_{1}+TS_{2}=(\Sigma^{\prime},T^{\prime})\] \[\text{where }\ \Sigma^{\prime}=(A_{1}\cup A_{2},D_{1}\cup D_{2}), \text{ and }\] \[T^{\prime}=\{\tau\ |\ \tau\in T_{1}\vee\tau\in T_{2}\}\]
* their parallel composition is the system: \[D_{1}D_{2}^{\circ}=D_{1}\cup D_{2}\cup\{(a_{1},a_{2}),(a_{2},a_{1})\mid a_{1} \in A_{1},a_{2}\in A_{2}\}\]0 \[D_{1}D_{2}^{\circ}=D_{1}\cup D_{2}\cup\{(a_{1},a_{2}),(a_{2},a_{1})\mid a_{1} \in A_{1},a_{2}\in A_{2}\}\]1 \[D_{1}D_{2}^{\circ}=D_{1}\cup D_{2}\cup\{(a_{1},a_{2}),(a_{2},a_{1})\mid a_{1} \in A_{1},a_{2}\in A_{2}\}\]2  
**Example 2**. : _Consider the following trace systems : \(TS_{0}=((A_{0},D_{0}),T_{0})\), \(TS_{1}=((A_{1},D_{1}),T_{1})\), and \(TS_{2}=((A_{2},D_{2}),T_{2})\), with \(A_{0}=\{a\}\), \(D_{0}=\{(a,a)\}\) and \(T_{0}=\{[a]\}\); \(A_{1}=\{a,b\}\), \(D_{1}=\{(a,a),(b,b),(a,b),(b,a)\}\) and \(T_{1}=\{[ab]\}\); \(A_{2}=\{b,c\}\), \(D_{2}=\{(b,b),(c,c),(b,c),(c,b)\}\) and \(T_{2}=\{[bc]\}\). \(TS_{0}.TS_{2}\) is the trace system \(TS_{3}=((A_{3},D_{3}),T_{3})\) with \(A_{3}=\{a,b,c\}\), \(D_{3}=\{(a,a),(b,b),(c,c),(a,b),(b,a),(a,c),(c,a),(b,c),(c,b)\}\) and \(T_{3}=\{[abc]\}\). \(TS_{0}+TS_{2}\) is the trace system \(TS_{6}=((A_{6},D_{6}),T_{6})\) with \(A_{6}=\{a,b,c\}\), \(D_{6}=\{(a,a),(b,b),(c,c),(b,c),(c,b)\}\) and \(T_{6}=\{[a],[bc]\}\). \(TS_{1}\|TS_{2}\) is the trace system \(TS_{4}=((A_{4},D_{4}),T_{4})\) with \(A_{4}=\{a,b,c\}\), \(D_{4}=\{(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,b)\}\) and \(T_{4}=\{[abc]\}\). \(TS_{0}\|TS_{2}\) is the trace system \(TS_{5}=((A_{5},D_{5}),T_{5})\) with \(A_{5}=\{a,b,c\}\), \(D_{5}=\{(a,a),(b,b),(c,c),(b,c),(c,b)\}\) and \(T_{5}=\{[abc]\}\). The expansion of the partial traces is obtained through the following definition: a completion step is performed by prefixing each hole \(\lfloor\ \rfloor_{T}\) in the partial trace by means of an element of the trace language \(T\); the same occurs for the holes possibly contained in \(T\). Each expansion of the partial trace maintains the capability of a further expansion for each hole. **Definition 1** (one-unfolding). : _Consider \(TS=((A,D),T)\) and \(\sigma\in A^{*}\), all the possible one-unfoldings of \(\sigma\), denoted by \(\widehat{\sigma}\), correspond to the set \(\mathcal{U}(\sigma,S)\), obtained as follows from an initial value of \(S=\emptyset\):_  
\[\mathcal{U}(\sigma,S)=\left\{ \begin{array}{ll}\sigma&\mbox{if $\sigma$ contains no hole or}\\ &\forall\ \lfloor\ \rfloor_{x}\in\sigma,\ x\in S\\ \\ \mathcal{U}(\sigma\left.\left[{}^{\sigma_{1}\ \lfloor\ \rfloor_{x}}\right/_{ \lfloor\ \rfloor_{x}}\right],S\cup\{x\})&\\ \cdots&\mbox{if $\lfloor\ \rfloor_{x}\in\sigma,\ x\
ot\in S,\forall i\in[1..n], \sigma_{i}\in x$}\\ \\ \mathcal{U}(\sigma\left.\left[{}^{\sigma_{n}\ \lfloor\ \rfloor_{x}}\right/_{ \lfloor\ \rfloor_{x}}\right],S\cup\{x\})&\end{array}