Azioni interne ed esterne

Un'azione rappresenta un passo di computazione che viene fatto da un sistema per poter andare da uno stato all'altro. Nella maggior parte delle teorie algebriche, le azioni costituiscono un'interazione con l'ambiente esterno tramite determinate porte del sistema, oppure rappresentano una computazione interna.

In genere un'azione si indica con lo stesso simbolo della porta su cui agisce, perciò se denotiamo l'insieme delle porte nel sistema considerato con il simbolo $\Lambda$, si trova che l'insieme di tutte le azioni visibili è il seguente:

$$Act \:=\: \{\alpha \::\: \alpha \in \Lambda\}$$

La computazione interna che abbiamo introdotto è invece un'azione che viene eseguita nel sistema, ma in modo che nessun osservatore esterno possa vederla. Il simbolo utilizzato per questa azione è $\tau$, perciò se vogliamo indicare l'insieme di tutte le azioni possibili si utilizza la notazione $\: Act \cup \{\tau\} \:$ (che spesso si abbrevia con $Act_\tau$).

Questa transizione invisibile ha grande importanza nello studio delle equivalenze tra sistemi perché può essere considerata come quelle esterne oppure può avere un trattamento proprio a seconda del tipo di equivalenza che si sta analizzando. In questi ultimi casi si deve aggiungere la notazione $\varepsilon$ che indica assenza di azioni visibili; quindi $\varepsilon$ indica la possibilità di fare zero o più azioni $\tau$ ( $\varepsilon$ si utilizza quindi nello studio di equivalenze di osservazione).

Dal momento che una transizione tra due stati è accompagnata da un'azione, se dal processo $P$ si passa a $Q$ tramite $\:\alpha \in Act_{\tau}$, si parla di derivazione e si indica in questo modo:

$$P \stackrel{\alpha}{\longrightarrow} Q$$

Se per passare da un processo all'altro servono più azioni si può anche utilizzare $s = (\alpha_1 \cdots \alpha_n)$ nella derivazione.

Nel caso in cui ci interessi il punto di vista di un osservatore esterno, le azioni interne dovranno essere ignorate nelle transizioni. Quindi si può avere la discendenza da P a Q tramite l'azione visibile $\:\alpha \in Act$:

$$P \stackrel{\alpha}{\Longrightarrow} Q$$

L'$\alpha$-discendenza corrisponde alla derivazione di $\alpha$, ma preceduta e seguita da zero o più azioni interne, ovvero:

$$P (\stackrel{\tau}{\longrightarrow})^* \stackrel{\alpha}{\longrightarrow} (\stackrel{\tau}{\longrightarrow})^* Q$$

Anche in questo caso possiamo utilizzare la sequenza di azioni visibili $s = (\alpha_1 \cdots \alpha_n)$.

L' $\varepsilon$-discendenza invece corrisponde alla derivazione di zero o più $\tau$:

$$P \stackrel{\varepsilon}{\Longrightarrow} Q$$

In alcuni casi può essere interessante soltanto la capacità da parte del processo P di derivare o discendere un'azione $\alpha$, mentre non ha importanza quale stato viene raggiunto. Queste situazioni "più generiche" sono indicate nei seguenti modi:

$$P \stackrel{\alpha}{\longrightarrow} \qquad \qquad \qquad P \stackrel{\alpha}{\Longrightarrow}$$

Definizione 2..2   Un processo $P$ si dice stabile se nel suo stato iniziale non può eseguire una derivazione $\tau$. In questi casi si utilizza la notazione $P \stackrel{\tau}{\not\longrightarrow}$.

In alcune algebre di processi (tra le quali anche CCS) le azioni esterne si dividono in azioni di input e azioni di output.

Quando un processo esegue un'azione di input, significa che esso riceve un segnale su una determinata porta $\alpha$ ed in genere si indica l'azione proprio con il simbolo $\alpha$. Nel caso dell'output, invece, è il processo stesso che emette il segnale attraverso una porta $\alpha$ ed in questo caso il simbolo viene soprabarrato ( $\overline{\alpha}$).

$\alpha$ ed $\overline{\alpha}$ sono dette azioni complementari ed hanno un ruolo fondamentale nella comunicazione tra due processi che agiscono in parallelo.

Indicheremo con $\overline{Act}$ l'insieme delle azioni complementari di $Act$, e con $\mathcal{L}$ l'unione di questi due insiemi: $\mathcal{L} = Act \cup \overline{Act}$. Inoltre, dato un processo $p$, si indicherà con $\mathcal{L}(p)$ l'insieme delle azioni di $p$.

Esempio Bill-Ben 2: Riprendendo l'esempio introdotto per gli LTS, si osserva facilmente che le azioni visibili sono $play$ e $work$, mentre l'unica azione interna del sistema è $\tau$. Se le azioni visibili sono degli output, in alcune algebre (compresa CCS) si scriverà $\overline{play}$ e $\overline{work}$.

Alcune derivazioni ovvie sono le seguenti:

$$q_0 \stackrel{play}{\longrightarrow} q_1 \:\qquad q_0 \stackrel{... ...l{play}{\longrightarrow} q_3 \:\qquad q_3 \stackrel{\tau}{\longrightarrow} q_4$$

Le tre discendenze più interessanti sono invece:

$$q_1 \stackrel{work}{\Longrightarrow} q_4 \qquad\qquad q_2 \stack... ...ongrightarrow} q_4 \qquad\qquad q_3 \stackrel{\varepsilon}{\Longrightarrow}q_4$$