Description

Il contributo dell’unità di Palermo al progetto di ricerca riguarda principalmente gli aspetti combinatorici e algoritmici della Teoria degli Automi e dei Linguaggi Formali. Esso si inserisce nelle linee di ricerca "Codici, combinatoria delle parole e delle strutture complesse" e "Linguaggi e strutture bidimensionali" del progetto. L’unità di Palermo si propone di affrontare lo studio di tali linee di ricerca con un approccio che prevede sia un’analisi combinatorica ed algoritmica dei problemi trattati sia l’applicazione dei risultati ottenuti in contesti applicativi nei quali i problemi si trovano inseriti e motivati. Più in dettaglio, per ciascuna di tali linee, descriviamo sinteticamente il contenuto, gli obiettivi e gli approcci che intendiamo sviluppare si prevede di sviluppare. A2) Codici, Combinatoria delle Parole e delle Strutture Complesse La ricerca sulla combinatoria delle parole sarà sviluppata strettamente in relazione con alcuni contesti applicativi come, per esempio, la Biologia Computazionale, la Linguistica e la Compressione Dati. Verrà affrontato infatti il problema del Fragment Assembly, ovvero della ricostruzione di una sequenza a partire da un sottoinsieme dei suoi fattori, analizzandone anche l'applicabilità nell'ambito biologico. Lo studio combinatorico della trasformata di Burrows-Wheeler, inoltre, sarà da supporto sia per lo sviluppo di ricerche su nuovi paradigmi di compressione sia per la costruzione di misure di similarità tra sequenze. Tali misure costituiranno un utile strumento sia per il confronto di sequenze teoriche classiche che per l'analisi di sequenze reali, come le sequenze biologiche o testi in linguaggio naturale. In questo senso l'approccio con cui questa unità si propone di affrontare lo studio della combinatoria su parole è complementare alla ricerca sviluppata dall’unità di Salerno, dove sono presi in considerazione principalmente gli aspetti matematici. Alcune delle ricerche più orientate alle applicazioni, come ad esempio la costruzione di un indice approssimato e il suo utilizzo per problemi di pattern matching approssimato sono collegate ad alcune ricerche sviluppate dall'unità di Milano Statale. Nell'ambito della teoria dei codici, l'unità si propone di proseguire lo studio delle condizioni di decifrabilità debole e di investigare su problemi algoritmici e teorici legati alla decomposizione dei codici in componenti non ambigue e totalmente ambigue. Tali ricerche sono connesse con quelle sviluppate dall'unità di Salerno. A4) Linguaggi e Strutture bidimensionali La ricerca sui linguaggi e sulle strutture bidimensionali, è complementare a quella sviluppata dall’unità di Firenze, dove sono presi in considerazione principalmente gli aspetti relativi all’enumerazione delle strutture, ed è anche complementare a quella portata avanti dall’unità di Milano Politecnico e dall'unità di Salerno, dove l’interesse principale è sviluppare modelli orientati all’applicazione e motivati da problemi di analisi di immagini ed approfondire lo studio dei relativi fondamenti teorici, rispettivamente. In collaborazione con l'unità di Milano Politecnico e di Salerno, per esempio, l'unità di Palermo di propone di generalizzare al bidimensionale nozioni di riconoscibilità, alcune classi di grammatiche context-free e i relativi risultati introdotti in ambito unidimensionale. In collaborazione con l'unità di Firenze, invece, si proseguirà lo studio dei polyomini k-convessi, sia da un punto di vista enumerativo sia nel contesto della tomografia discreta.

Layman's description

Automi e Linguaggi Formali: aspetti matematici e applicativi
StatusActive
Effective start/end date1/1/05 → …