Italiano English
5-7 settembre 2011
Villa Toeplitz, Varese

PRIN 2007

Aspetti matematici e applicazioni emergenti degli automi e dei linguaggi formali.

Presentazione del progetto

Questo progetto di ricerca si concentra su linguaggi formali e automi e mira a far progredire la teoria su questi temi e le loro applicazioni a problemi tecnologici e scientifici. La teoria dei linguaggi formali e degli automi, uno dei più affermati campi in Computer Science, offre ancora complessi problemi aperti e linee di ricerca in molte direzioni.

Infatti, da un lato, sono emerse nuove applicazioni di concetti della teoria degli automi, in aggiunta alle più classiche applicazioni come il pattern matching, l'analisi sintattica e la validazione di software. Queste includono i sistemi di analisi e di verifica, l'elaborazione dei linguaggi naturali, l'information retrieval, la compressione dei dati, e il controllo di sistemi a eventi discreti. Inoltre, le nuove sfide per la teoria degli automi comprendono la biologia, la sicurezza delle reti, il calcolo quantistico, la tomografia, e l'elaborazione di immagini.

D'altra parte, alcune profonde questioni della teoria classica sono ancora aperte, e nuovi problemi teorici derivano anche dalle applicazioni. Questo è il motivo per cui i fondamenti matematici di questa teoria si basano sulle aree più avanzate della matematica. Mentre nei primi anni sessanta si utilizzavano solo la teoria elementare dei grafi e la combinatoria, successivamente sono stati introdotti nuovi strumenti di algebra non commutativa, logica, teoria della probabilità e dinamica simbolica, e gli sviluppi più recenti prendono in prestito idee anche dalla topologia e dalla geometria. Per esempio, la combinatoria delle parole finite o infinite di simboli di un alfabeto finito è stata notevolmente sviluppata negli ultimi anni ed è stata estesa a strutture combinatorie più generali delle parole, e cioè agli alberi e alle immagini.

Ovviamente, sviluppi tecnici significativi necessitano progressi teorici significativi. Così, dopo la comparsa delle nuove applicazioni elencate sopra, si avverte ancor più l'esigenza di risultati fondamentali. L'obiettivo del progetto è quello di sviluppare la ricerca nel campo dei linguaggi formali e degli automi (sia per i modelli teorici sia per le applicazioni in campi specifici) e integrare le diverse competenze delle unità che partecipano al progetto. Il progetto di ricerca si concentra su un numero limitato di argomenti. Più in particolare, si prevede di sviluppare le seguenti linee di ricerca:

  1. Modelli di automi, serie formali, e loro proprietà:
    • Automi quantistici
    • Misure di complessità descrittiva di linguaggi
    • Automi dei suffissi e loro applicazioni all'indicizzazione di testi
    • Automi a petali e loro applicazioni ai codici a lunghezza variabile
    • Automi di Schutzenberger e relativi algoritmi
    • Parole k-sincronizzanti e k-collassanti
    • Tecniche di manipolazione simbolica per linguaggi formali.
  2. Parole, codici e strutture combinatorie.
    • Proprietà combinatorie, strutturali ed aritmetiche di parole sturmiane e loro generalizzazioni
    • Regolarità evitabili e ripetitività in parole infinite
    • Statistiche di pattern
    • Trasformata di Burrows-Wheeler
    • Applicazioni della combinatoria delle parole alla Compressione Dati
    • Estensioni della combinatoria delle parole agli alberi etichettati
    • Combinatoria enumerativa ed algebrica
    • Generazione esaustiva e codici Gray
    • Proprietà strutturali di codici a lunghezza variabile
  3. Grammatiche e rappresentazioni non convenzionali di linguaggi formali.
    • Linguaggi di parentesi e grammatiche libere dal contesto
    • Funzioni di conteggio di linguaggi liberi dal contesto
    • Grammatiche probabilistiche libere dal contesto e loro applicazioni all'elaborazione di linguaggi naturali
    • Schemi di traduzione guidati dalla sintassi (SDTS), automi di alberi e loro applicazioni alla traduzione di linguaggi naturali
    • Modelli associative per la definizione di linguaggi: Grammatiche Consensuali, Associative Language Descriptions (ALD)
    • Sistemi di calcolo molecolare
    • Caratterizzazione di linguaggi regolari generati da splicing systems finiti (lineari e circolari)
  4. Linguaggi e strutture bidimensionali
    • Linguaggi tiling riconoscibili
    • Modelli deterministici e non ambigui
    • Serie formali in 2D
    • Generalizzazione di espressioni regolari in 2D
    • Problemi di decisione per linguaggi bidimensionali
    • Classificazione di immagini e pattern recognition basati su grammatiche e tiling, e loro applicazioni
    • Proprietà combinatorie dei permutomini
    • Problemi di unicità e stabilità per algoritmi di ricostruzione in tomografia geometrica e discreta
    • Automi cellulari, dinamica simbolica a linguaggi associati, problemi di decisione
  5. Modelli formali e sistemi distribuiti
    • Linguaggi traccia
    • Modelli di calcolo parallelo basati sulla teoria delle tracce motivate dalla compilazione di codice
    • Modelli per l'analisi del web
    • Analisi e validazione di sistemi: modelli e loro problemi di decisione per sistemi a stati infiniti
    • Logiche temporali soddisfacibili per la validazione in tempo reale di sistemi