Indietro

ⓘ Alfabeto concorrente




                                     

ⓘ Alfabeto concorrente

Nella teoria dei linguaggi formali, e in particolare nellambito dei linguaggi traccia, un alfabeto concorrente è costituito da una coppia {\displaystyle } 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 a, b ∈ Σ {\displaystyle a,b\in \Sigma }, se ∈ θ {\displaystyle \in \theta } si dice che a {\displaystyle a} e b {\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 a {\displaystyle a} e b {\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 sé stesso irriflessività;
  • nel caso a {\displaystyle a} possa essere elaborato concorrentemente rispetto a b {\displaystyle b}, lo stesso deve valere per b {\displaystyle b} rispetto ad a {\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.