Alfabeto concorrente

Template:F Nella teoria dei linguaggi formali, e in particolare nell'ambito dei linguaggi traccia, un alfabeto concorrente è costituito da una coppia $(\mathrm{\Sigma },\theta )$ in cui $\mathrm{\Sigma }$ rappresenta un generico alfabeto e $\theta$ rappresenta una relazione binaria su $\mathrm{\Sigma }$ detta relazione di indipendenza. Dati due simboli $a,b\in \mathrm{\Sigma }$, se $(a,b)\in \theta$ si dice che $a$ e $b$ sono indipendenti.

La relazione di indipendenza $\theta$ è definita come una relazione binaria su $\mathrm{\Sigma }$ antiriflessiva e simmetrica. Il fatto che, dal punto di vista della concorrenza, due simboli $a$ e $b$ indipendenti possano essere elaborati in un ordine qualunque oppure in parallelo spiega perché $\theta$ sia definita in questo modo, infatti:

• un simbolo non può essere elaborato concorrentemente a sé stesso (irriflessività);
• nel caso $a$ possa essere elaborato concorrentemente rispetto a $b$, lo stesso deve valere per $b$ rispetto ad $a$ (simmetria).

Il concetto di alfabeto concorrente costituisce una generalizzazione del concetto di alfabeto, il quale può essere visto come un alfabeto concorrente con la relazione di indipendenza vuota.