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 (\Sigma,\theta) in cui \Sigma rappresenta un generico alfabeto e \theta rappresenta una relazione binaria su \Sigma detta relazione di indipendenza. Dati due simboli a,b\in\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 \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.