Salta al contenuto principale
Passa alla visualizzazione normale.

INF INF/01 "AUTOMI, LINGUAGGI FORMALI E COMBINATORIA DELLE PAROLE"

5-feb-2015

Ascolta

La ricerca riguarda la Teoria degli Automi e dei Linguaggi Formali, una delle aree dell'Informatica più consolidate, che trae origine da problematiche relative ai primi computer, ai sistemi di comunicazione ed ai linguaggi di programmazione. Successivamente, gli sviluppi della tecnologia informatica hanno incrementato la necessità di esplorare nuovi modelli specifici e hanno stimolato nuovi spunti teorici. Quest'area di ricerca si trova al crocevia fra l'informatica teorica, la matematica e le applicazioni. Da un punto di vista matematico, essa utilizza prevalentemente la Combinatoria delle Parole, ma anche nuovi strumenti concettuali dell'algebra non commutativa, della logica, della teoria delle probabilità. Il progetto di algoritmi su stringhe ne rappresenta un aspetto complementare, motivato dalle potenziali applicazioni scientifiche che includono, fra le altre, la codifica, la compilazione, la verifica del software, la compressione dati, la bioinformatica e la ricerca del web. Le linee di ricerca riguardano prevalentemente gli aspetti combinatori e algoritmici degli automi e dei linguaggi, e prendono anche in considerazione alcuni ambiti applicativi. Le principali tematiche di ricerca riguardano:
- modelli di Automi, con particolare riferimento ai problemi di minimizzazione e di sincronizzazione;
- la Combinatoria delle Parole, con applicazioni ai linguaggi formali ed allo string processing;
- algoritmi su stringhe, con applicazioni alla Compressione Dati e alla Bionformatica
- i Linguaggi e le Strutture 2D, come i poliomini, con applicazioni a problemi di Tomografia Discreta;
- la Teoria dei Codici, anche in riferimento a problemi di comunicazione.