Automi e Linguaggi Formali: Aspetti Matematici e Applicativi

Progetto: Research project

Dettagli progetto

Description

La teoria degli automi e dei linguaggi formali è una delle più consolidate aree dell’ Informatica. La ricerca in questo settore è stata sviluppata grazie alla stretta interazione tra teoria e applicazioni. Il contributo dell’unità di Palermo al progetto di ricerca riguarda principalmente gli aspetti combinatori e algoritmici delle parole e degli automi, sviluppati in collegamento con alcuni contesti applicativi.Gli obiettivi di ricerca sono brevemente descritti di seguito in relazione ai temi di ricerca del progetto nazionale.A1) Modelli di automi e serie formaliL'obiettivo è di investigare nel campo degli automi con output. Il modello più semplice di automa con output è l’automa di Moore. Per via delle sue numerose applicazioni in molti settori, la sua minimizzazione risulta di grande interesse. In questo ambito analizziamo alcune generalizzazioni degli algoritmi di minimizzazione di Hopcroft e Brzozowski su automi di questo tipo.Un difficile problema aperto nella teoria dei linguaggi regolari è caratterizzare la più piccola famiglia di linguaggi contenenti i singleton e chiusa rispetto alle operazioni booleane, concatenazione e shuffle. Tale famiglia comprende strettamente i linguaggi star-free. Ciò porta ad indagare sulle condizioni sotto cui lo shuffle di due linguaggi star-free è star-free.Un altro problema fondamentale nella teoria degli automi è la famosa congettura di Cerny sugli automi sincronizzanti. Lo studio di questo problema su alcune particolari famiglie di automi porta ad indagare sulla minima parola incompletabile. A2) Combinatoria di parole e codiciIl teorema della fattorizzazione critica (CFT) è uno dei risultati più importanti sulle parole. Il concetto di punto critico è cruciale nel CFT. L'obiettivo principale della nostra ricerca è quello di classificare le parole finite ed infinite in termini del numero di occorrenze dei punti critici.Un altro tema di ricerca è legato alla trasformata di Burrows-Wheeler (BWT) e alla sua estensione ad un multiset di parole (EBWT). In particolare, analizziamo le applicazioni della EBWT alle misure di similarità di sequenze.Nel campo della teoria dei codici una direzione primaria di ricerca riguarda lo studio delle condizioni per la decomponibilità di un codice prefisso. Per quanto riguarda la decodifica dei codici bidirezionali prefissi binari cerchiamo di estendere il metodo di Girod ai codici prefissi su qualsiasi alfabeto, e ai codici con ritardo di decifrazione limitato.A4) Generazione, enumerazione e compressione di strutture combinatorieIl nostro interesse in questa linea di ricerca, da un lato sarà diretto verso lo studio combinatorio di parole e linguaggi 2D e, dall'altro, sarà rivolto alle metodologie per l'analisi dei dati massivi.La teoria delle parole Sturmiane può essere estesa attraverso lo studio di funzioni biiettive bidimensionali che rappresentano rotazioni di matrici invece di linee cellulari. Un'analisi combinatoria profonda potrebbe portare ad una teoria rigorosa sulle rotazione di immagini.La ricerca sui linguaggi bidimensionali verterà principalmente sulla classe REC dei linguaggi riconosciuti da “tiling systems”. In particolare, si intende proseguire lo studio delle corrispondenze tra linguaggi di stringhe e linguaggi bidimensionali utilizzati per riconoscerli.In riferimento alle questioni relative alla gestione e all'analisi dei dati massivi, un primo tema è focalizzato sulla compressione di testi. In particolare, studiamo il modello di “dizionario-symbolwise”, che copre la maggior parte degli attuali algoritmi di compressione. Un'altra linea di ricerca è

Layman's description

L'unità di Palermo apporta al progetto le proprie competenze ed esperienza nel campo della teoria dei linguaggi formali e automi, nella combinatoria su parole e nella sua applicazione ad ambiti applicativi come la compressione e l'analisi di sequenze biologiche. L'interazione e la sinergia con le altre unità del consorzio consentiranno di dare un apporto significativo alle tematiche del progetto. In particolare, l'unità di Palermo interverrà nel progetto sviluppando temi di ricerca nelle seguenti linee.A1) Modelli di automi e serie formaliUno degli obiettivi del nostro progetto è lo studio degli automi con output visti come calcolatori di funzioni e non come riconoscitori di linguaggi. Il modello più semplice è l’automa di Moore. Viste le diverse applicazioni in molti settori, ad esempio system modeling, elaborazione dei linguaggi naturali, verifica dei sistemi, machine learning, è utile una rappresentazione compatta di tale modello, pertanto la minimizzazione di tale oggetto diventa di grande interesse. Distinguiamo gli automi di Moore deterministici e quelli non deterministici.Per quanto riguarda gli automi di Moore deterministici, vogliamo formulare una possibile generalizzazione dell’algoritmo di minimizzazione di Hopcroft a tali automi prendendo in considerazione problemi riguardanti l’implementazione, la complessità di tempo e la tightness. Il caso di automi accettori può essere considerato come un caso particolare in cui l'alfabeto di output è binario ({accettato, rifiutato}). In tale caso, la costruzione di una famiglia di automi associata a parole di Fibonacci circolari prova la tightness dell’algoritmo. Nel caso generale, il problema di trovare se la tightness possa essere raggiunta richiede di estendere la precedente costruzione introducendo classi di parole, su alfabeti con più di due lettere, che condividono le proprietà speciali delle parole di Fibonacci che consentono raggiungere la tightness nel caso binario. Siamo interessati anche ad analizzare come una nostra nuova generalizzazione dell’algoritmo di Brzozowski funziona su tali automi. Nel caso di automi di Moore non deterministici, un ampio campo di indagine riguarda la struttura algebrica dell'alfabeto di uscita. In particolare, vogliamo prendere in considerazione alfabeti di uscita che siano reticoli in modo tale che per ogni input uno solo degli output "vinca". Vogliamo anche indagare su quali tipi di reticolo le operazioni classiche sugli automi possano essere applicate con successo e l'algoritmo di Brzozowski funziona. Le ricerche condotte in quest’ambito sono connesse a quelle relative alla complessità descrizionale svolte dall’unità di Milano Statale.Un importante problema aperto della teoria dei linguaggi regolari riguarda la caratterizzazione della più piccola famiglia di linguaggi che contiene i "singleton" ed è chiusa rispetto alle operazioni booleane, il prodotto e lo shuffle. Tale famiglia include strettamente quella dei linguaggi star-free. Pertanto un primo passo nel problema generale è di indagare sotto quali condizioni lo shuffle di due linguaggi star-free è ancora star-free. Noi analizzeremo il caso speciale in cui i due linguaggi star-free sono sottomonoidi ciclici. Ciò conduce a nuovi problemi di combinatoria delle parole. In particolare, noi intendiamo caratterizzare le coppie di parole primitive u, v tali che lo shuffle di u* e v* è un linguaggio star-free (o, equivalentemente, aperiodico). Lo studio delle potenze che appaiono in tale shuffle presenta interessanti analogie con il teorema di Lyndon-Schutzenberger.Un problema fondamentale nella t

Key findings

Tecnologie dell'Informazione e delle Comunicazioni (ICT)
StatoAttivo
Data di inizio/fine effettiva2/1/13 → …