Utente:Alscor/Monoide libero parzialmente commutativo

Nella teoria dei linguaggi formali, dati:

• un alfabeto ${\displaystyle \Sigma }$, i.e. un insieme di simboli indicati mediante le prime lettere (minuscole) dell'alfabeto come a, b, c, etc.,
• l'operazione "${\displaystyle \cdot }$" di concatenazione tra stringhe, secondo la quale, date x=ab e y=cd, x ${\displaystyle \cdot }$ y=abcd e
• la stringa vuota ${\displaystyle \epsilon }$,

indichiamo con ${\displaystyle (\Sigma ^{*},\cdot ,\epsilon )}$ un monoide libero nel quale ${\displaystyle \Sigma ^{*}}$ rappresenta l'insieme delle stringhe sull'alfabeto ${\displaystyle \Sigma }$.

Dato ora un alfabeto concorrente ${\displaystyle (\Sigma ,\theta )}$, ottenuto affiancando all'alfabeto ${\displaystyle \Sigma }$ definito in precedenza una relazione di indipendenza ${\displaystyle \theta }$, possiamo definire su ${\displaystyle \Sigma ^{*}}$ una congruenza ${\displaystyle \equiv _{\theta }}$ tale che due stringhe x,y in ${\displaystyle \Sigma ^{*}}$ sono congruenti se e solo se esiste una sequenza di stringhe w₀,w₁,...,w_m tale che: x=w₀, y=w_m e (per i=1,...,m) la stringa w_i è ottenuta da w_i-1 scambiando tra loro due simboli adiacenti indipendenti.

La congruenza ${\displaystyle \equiv _{\theta }}$ suddivide ${\displaystyle \Sigma ^{*}}$ in classi di equivalenza e definisce un insieme quoziente ${\displaystyle \Sigma _{/\equiv _{\theta }}^{*}}$ che prende il nome di monoide libero parzialmente commutativo o (monoide di tracce) indicato con ${\displaystyle F(\Sigma ,\theta )}$. Ciascun elemento di ${\displaystyle F(\Sigma ,\theta )}$ (i.e. ciascuna classe di equivalenza) prende il nome di traccia.

[[Categoria:Linguaggi formali]]