Semigruppi Liberi e Teoria dei Codici

Programma del corso

Semigruppi e monoidi. Il teorema di associatività generale. Il gruppo degli elementi invertibili di un monoide. Zero di un semigruppo. Elementi idempotenti. Fattori sinistri (destri) di un elemento di un semigruppo. Semigruppi cancellativi. Semigruppi commutativi. Condizioni necessarie e sufficienti affinché un semigruppo sia un gruppo. Il semigruppo delle parti di un semigruppo. Prodotto diretto di semigruppi e di monoidi. Il semigruppo e il monoide delle parole su un alfabeto. Il monoide delle relazioni binarie su un insieme. Il monoide delle trasformazioni di un insieme. Il monoide delle funzioni parziali in un insieme. Sottosemigruppi e sottomonoidi. Sottosemigruppi e sottomonoidi generati da una parte di un semigruppo. Semigruppi finitamente generati. Semigruppi monogenici. Ordine di un elemento di un semigruppo. Indice e periodo di un elemento di ordine finito. Semigruppi periodici. Omomorfismi di semigruppi e di monoidi. Immersione di un semigruppo numerabilmente generato in un semigruppo 2-generato. Congruenze in un semigruppo. Semigruppi e monoidi quoziente. Teoremi di omomorfismo nei semigruppi e nei monoidi. Ideali di un semigruppo. Ideali generati da una parte di un semigruppo. Congruenze e quozienti di Rees. Il semigruppo dei fattori di una parte propria di un semigruppo. Congruenze sintattiche. Semigruppi sintattici. Semianelli. Il semianello tropicale. Il semianello delle parti di un monoide. Il semianello delle relazioni binarie in un insieme. Il semianello delle serie formali su un alfabeto a valori in un dato semianello. Relazione riflessiva, simmetrica, transitiva, di equivalenza generate da una relazione. Il reticolo delle congruenze di un semigruppo. Congruenza generata da una relazione in un semigruppo.

Semigruppi e monoidi liberi. Insiemi linearmente indipendenti e basi. Unicità della base e sue caratterizzazioni. Proprietà universale dei semigruppi e dei monoidi liberi. Esistenza ed unicità a meno di isomorfismi del semigruppo libero e del monoide libero di base avente assegnata cardinalità. Lunghezza di un elemento in un monoide libero. Lemma di Levi. Lemma di Lyndon e Schützenbeger. Sottomonoidi di monoidi liberi. Elementi irriducibili. Caratterizzazioni dei sottomonoidi liberi di un monoide libero. Teorema di Schützenbeger. Parti liberabili di un monoide. Sottomonoidi unitari a sinistra (unitari a destra, biunitari) del monoide delle parole su un alfabeto. Inviluppo libero di un insieme di parole su un alfabeto. Il teorema del difetto. Presentazioni di semigruppi e di monoidi. Il monoide commutativo libero. Il monoide biciclico.

Parole. Lunghezza e fattori di una parola. Prefissi e suffissi. Sottoparole e loro molteplicità. Parole rovesciate. Parole palindrome. Parole coniugate. Parole permutabili. Parole primitive. Esistenza ed unicità della radice di una parola non vuota. Ordinamenti nei monoidi liberi: ordine prefissiale, ordine suffissiale, ordine fattoriale, ordine di divisione, ordine lessicografico, ordine militare.

Codici. Caratterizzazioni dei codici. Codici uniformi. Codici di ordine 2. Codici prefissi, suffissi, bifissi e loro caratterizzazioni. Teorema di Sardinas e Patterson. Distribuzioni di Bernoulli su un alfabeto. Misura degli insiemi di parole indotta da una distribuzione di Bernoulli. Disuguaglianza di Kraft-McMillan. Funzione di struttura su un insieme di parole. Codici massimali. Insiemi di parole densi (densi a sinistra, densi a destra). Insiemi di parole completi (completi a sinistra, completi a destra). Parole primarie. Completezza di un codice massimale. Massimalità di un codice completo e non denso. Codici prefissi massimali e loro caratterizzazioni. Codici sincronizzanti. Codici binari a blocchi: decodifica per massima probabilità, distanza di Hamming, codici error-detecting, codici error-correcting.



Testo consigliato:

A. de Luca, F. D'Alessandro, Teoria degli Automi Finiti, Springer, Milano, 2013.



Per approfondimenti:

J. Berstel, D. Perrin, Theory of Codes, Academic Press, London, 1985;

J.M. Howie, An Introduction to Semigroup Theory, Academic Press, London, 1976;

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, 1983.