Linguaggi Formali e Automi: Strutture Matematiche e Orientamenti Applicativi

Progetto: Research project

Dettagli progetto

Layman's description

Il progetto di ricerca che proponiamo è la naturale evoluzione del progetto PRIN 2009, valutato positivamente ma non finanziato, presentato con lo stesso titolo dal proponente del presente progetto. Il personale strutturato dell'Università di Palermo che partecipa al presente progetto è lo stesso di quello che partecipava al progetto PRIN 2009, con l'aggiunta della dott.ssa Giuseppa Castiglione, che partecipava già al quel progetto in qualità di assegnista di ricerca. La dott.ssa Giovanna Rosone, che partecipa al presente progetto in qualità di assegnista di ricerca, partecipava al PRIN 2009 in qualità di dottoranda. Gli altri partecipanti alla nostra unità di ricerca del PRIN 2009 non hanno titolo per partecipare al presente progetto, o perché docenti strutturati di altra sede universitaria, o perché non hanno più alcun rapporto formale con l'Università di Palermo. Le linee di ricerca che proponiamo sono una prosecuzione di quelle previste dal programma di ricerca della nostra unità del PRIN 2009 che aveva come titolo "Aspetti combinatorici e algoritmici degli Automi e dei Linguaggi Formali". Esse presentano qualche leggera variazione rispetto a quelle proposte nel PRIN 2009, sia per la naturale evoluzione delle tematiche di ricerca negli ultimi anni, sia perché alcune delle linee proposte nel PRIN 2009 si avvalevano di competenze che erano presenti in quel progetto (ricercatori delle altre sedi coordinate) e che non sono presenti in quello attuale. Il progetto che proponiamo verte sulla Teoria degli Automi e dei Linguaggi Formali (TALF), che è una delle aree dell'Informatica più consolidate. In tale area la ricerca si è sviluppata ed evoluta grazie alla stretta interazione tra teoria ed applicazioni. Da un lato concetti della teoria degli automi trovano molte applicazioni in biologia, fisica, tomografia, linguistica, ecc; dall'altro, gli sviluppi della tecnologia informatica incrementano la necessità di un'esplorazione di nuovi modelli specifici e stimolano nuovi spunti teorici. Il progetto di ricerca riguarda principalmente gli aspetti combinatorici e algoritmici della TALF, e prenderà anche in considerazione alcuni contesti applicativi, come, ad esempio, la bioinformatica e la compressione dati. In particolare, si svilupperanno le seguenti linee di ricerca: Modelli di Automi. E' nostro intento proseguire l'indagine sulla minimizzazione di automi a stati finiti deterministici(DFA). In particolare, ci dedicheremo all'analisi e al confronto di alcuni algoritmi di minimizzazione classici: algoritmi di Moore, di Hopcroft e di Brzozowski. Un aspetto finora poco esplorato è quello di prendere in considerazioni automi con output (automi di Moore). La minimizzazione di tali automi presenta problemi ancora aperti. Siamo, in particolare, interessati ai casi peggiori degli algoritmi di minimizzazione, e alle loro relazioni. Una linea di ricerca correlata riguarda la progettazione di algoritmi efficienti per la costruzione di automi "quasi" minimali per particolari famiglie di linguaggi, come, ad esempio, i linguaggi finiti. Questa linea di ricerca si inserisce nella più ampia problematica della complessità descrizionale di linguaggi regolari, che studia la taglia minima di espressioni regolari e automi. Un'altra linea di ricerca che intendiamo sviluppare riguarda un noto problema aperto della teoria degli automi: caratterizzare la più piccola famiglia di linguaggi che contiene i "singleton" ed è chiusa rispetto alle operazioni booleane, al prodotto ed allo shuffle. L'interesse di questo studio è anche legato alle applicazioni dell'operazione shuffle all'algebra dei processi ed alla verifica dei programmi. Combinatoria delle parole e codici. Nel campo della Combinatoria delle Parole, intendiamo portare avanti lo studio della Trasformata di Burrows-Wheeler (BWT) e la sua estensione a multiset di parole (EBWT). Siamo interessati a fornire caratterizzazi
StatoAttivo
Data di inizio/fine effettiva1/1/12 → …

Fingerprint

Esplora i temi di ricerca toccati da questo progetto. Queste etichette sono generate sulla base dei riconoscimenti/sovvenzioni sottostanti. Insieme formano una fingerprint unica.