Presentazione del progetto

Il progetto si propone di far avanzare la conoscenza della teoria degli automi e la sua applicabilità a problemi scientifici e tecnologici.

La ricerca utilizzerà sia approcci classici, come la combinatoria e i semigruppi, sia nuovi strumenti concettuali dell'algebra non commutativa, della logica, della teoria della probabilità e della dinamica simbolica. Potenziali applicazioni scientifiche includono fra le altre, la codifica, la biologia, le scienze cognitive e neurologiche, la compilazione e la verifica del software, le risorse del web.

La cooperazione interdisciplinare fra matematici, informatici teorici e ingegneri permetterà una sinergia tra la ricerca fondamentale e lo studio di nuovi modelli formali orientati alle applicazioni.

In uno scenario dove un gruppo di scienziati qualificato e di studenti di dottorato può comunicare e condividere sia le sfide provenienti da nuove applicazioni della teoria degli automi, sia le intuizione teoriche, questo programma catalizzerà progressi in entrambe le direzioni.

Evitando dispersioni sull'intero settore, sarà affrontato un campo limitato di direzioni di ricerca.

A1) Modelli di Automi, serie formali, e loro proprietà Studio di modelli computazionali quali gli automi quantistici, mediante l'analisi dei loro comportamenti descritti da linguaggi formali. Studio della complessità descrizionale di automi con vincoli di risorse. Proprietà algebriche di automi a stati finiti, con particolare attenzione allo studio mediante automi di semigruppi inversi. Studio di proprietà di serie formali razionali e olonomiche, con applicazioni alle statistiche di pattern e al conteggio e generazione casuale di parole in linguaggi di date classi.

A2) Codici, combinatoria su parole e strutture complesse. Applicazioni della combinatoria delle parole alla Compressione Dati, allo string matching approssimato, al Fragment Assembly Problem. Proprietà combinatorie, aritmetiche e strutturali delle parole Sturmiane. Proprietà d'ordine di classi di strutture quali cammini, permutazioni e partizioni. Problemi di enumerazione di permutazioni a motivo escluso. Caratterizzazione dei codici fattorizzanti mediante loro descrizione strutturale. Condizioni di decifrabilità più debole; Varietà di codici.

A3) Grammatiche context-free e rappresentazioni non convenzionali di linguaggi formali. Grammatiche XML e linguaggi XML. Miglioramento di costruzioni classiche di traduttori syntax-directed per linguaggi deterministici. Nuove estensioni del teorema di Higman. Problemi di base e algoritmici delle descrizioni basate su linguaggi associativi (Associative Language Descriptions, ALD); il problema aperto dell'inclusione dei regolari nella classe dei linguaggi ALD. Caratterizzazione dei linguaggi regolari generati dai sistemi finiti di splicing (lineare o circolare).

A4) linguaggi e strutture bidimensionali Studio di modelli formali recenti che estendono a due dimensioni le classiche definizioni di linguaggi Regolari e Context-Free. Più precisamente per i Tiling Systems (TS) e le Tile Rewriting Grammars (TRG), ricerca sugli automi corrispondenti e algoritmi di parsing, relazioni con altri modelli, generalizzazione di espressioni regolari a due dimensioni, caratterizzazioni di linguaggi unari, applicabilità ad analisi di immagini. Studio di alcune estensioni di polyomini L-convessi negli ambiti di ricerca classici della teoria dei polyomini.

A5) Modelli formali di sistemi distribuiti e temporizzati. La ricerca su modelli di automi adatti alla verifica e all'analisi di sistemi, in particolare su: Automi temporizzati ed estensioni a macchine con memoria illimitata, come quelle dotate di stack e gli automi dense counter; problemi di complessità rilevanti per il model checking. Ricerca su algoritmi per la parallelizzazione del codice per programmi rappresentati da modelli formali, cioè linguaggi traccia, e mediante trasformazioni affini.