Alfabeto concorrente

Da Wikipedia, l'enciclopedia libera.

Nella teoria dei linguaggi formali, e in particolare nell'ambito dei linguaggi traccia, un alfabeto concorrente è costituito da una coppia in cui rappresenta un generico alfabeto e rappresenta una relazione binaria su detta relazione di indipendenza. Dati due simboli , se si dice che e sono indipendenti.

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

  • un simbolo non può essere elaborato concorrentemente a sé stesso (irriflessività);
  • nel caso possa essere elaborato concorrentemente rispetto a , lo stesso deve valere per rispetto ad (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.