Equivalenza di traccia completa

Definizione 5..3 (Traccia completa)   La sequenza di azioni $s \in Act_{\tau}^*\:$ è una traccia completa per un processo $p$ se $\:p \stackrel{s}{\longrightarrow} p' \: \land \:p' \not\rightarrow$

Quindi si considerano soltanto le sequenze di azioni che partono da $p$ e raggiungono uno stato senza più transizioni possibili. L'insieme delle tracce complete di $P$ si indica con $CT(P)$.

Definizione 5..4 (Equivalenza di traccia completa)   Due processi $p$ e $q$ si dicono equivalenti di traccia completa, indicato come $p \sim_{ct} q$ se sono equivalenti di traccia ed hanno le stesse tracce complete, cioè:

$$p \sim_{ct} q \quad \Leftrightarrow \quad p \sim_t q \: \land \: CT(p)=CT(q)$$

Da questa definizione si intuisce banalmente che se due processi sono in relazione $\sim_{ct}$ allora essi sono sicuramente equivalenti di traccia. Però il contrario non è sempre vero e questo lo si capisce subito dal seguente semplice esempio:

$$\alpha.\:\beta\:.nil + \alpha.\:nil \:\sim_t\: \alpha.\:\beta\:.n... ...ad \alpha.\:\beta\:.nil + \alpha.\:nil \:\not\sim_{ct}\: \alpha.\:\beta\:.nil$$

infatti i due processi hanno le stesso tracce $\varepsilon$, $\alpha$ e $\alpha \beta$, ma a sinistra si trova la traccia completa $\alpha$ che non è presente nel processo di destra (in cui dopo $\alpha$ si può sempre fare una $\beta$-derivazione).