Alfabeto concorrente

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

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

• un simbolo non può essere elaborato concorrentemente a se stesso (irriflessività);
• nel caso ${\displaystyle a}$ possa essere elaborato concorrentemente rispetto a ${\displaystyle b}$, lo stesso deve valere per ${\displaystyle b}$ rispetto ad ${\displaystyle 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.