Investigación | Proyectos Financiados

ASPETTI MATEMATICI E APPLICATIVI NELLA TEORIA DEI CODICI E LINGUAGGI FORMALI.

Saranno affrontati i seguenti argomenti:1. Studio della relazione tra i codici massimali prefissi riconosciuti da automi finiti e l’operazione di decomposizione.Un codice massimale prefisso razionale (cioè riconosciuto da un automa finito) X può, in alcuni casi, essere ottenuto da un codice massimale prefisso finito, mediante l’operazione di decomposizione. Si intende stabilire se tale proprietà sia decidibile. Punto di partenza sarà un lavoro di Clelia De Felice, con Sabrina Mantaci e Antonio Restivo, in cui viene presentata una procedura, basata sull’automa minimale di X, che stabilisce se X è indecomponibile e, in caso contrario, costruisce codici razionali su cui X si decompone. 2. Estensione della teoria dei codici al caso bidimensionale. Si intende proseguire la ricerca sui codici bidimensionali iniziata in alcuni lavori di Marcella Anselmo con Dora Giammarresi e Maria Madonia, seguendo le linee tracciate dalla teoria dei codici di stringhe. Il risultato di indecidibilità per un codice bidimensionale anche finito suggerisce lo studio di sottofamiglie di codici per le quali l’appartenenza di un linguaggio diventi decidibile. In particolare ci si propone di estendere le nozioni di codice legate a problemi di sincronizzazione (quali i codici bifissi e comma-free). L’interesse sarà rivolto anche a codici di cardinalità infinita, ma riconoscibili in REC, studiando le relazioni della proprietà di univoca decifrabilità con il riconoscimento deterministico e non ambiguo. Nello studio dei codici di oggetti bidimensionali, particolare interesse rivestono i problemi combinatorici legati all’accavallamento fra picture e alle corrispondenti nozioni di prefisso, sottopicture e bordo di una picture. Si intendono ugualmente affrontare tali aspetti.3. Studio delle relazioni tra codici bifissi, combinatoria delle parole e teoria dei gruppi, continuando uno studio già intrapreso da Clelia De Felice, in collaborazione con Jean Berstel, Dominique Perrin, Christophe Reutenauer e Giuseppina Rindone in vari lavori pubblicati. Una recente estensione, oggetto di un lavoro in corso, considera il caso dei gruppi speculari, una classe più ampia dei gruppi liberi e inclusa nella classe dei gruppi virtualmente liberi. 4. Si intende studiare la congettura della fattorizzazione per la famiglia dei codici massimali finiti contenenti una potenza della lettera a con esponente primo, continuando la ricerca iniziata in vari lavori di Clelia De Felice.5. Per quanto riguarda i sistemi splicing circolari finiti, lo studio sarà rivolto in particolare alla caratterizzazione dei linguaggi regolari generati da sistemi splicing circolari finiti di tipo (1,3). In tali caso, le regole generative hanno una forma particolare, che permette di semplificarne l’applicazione, riducendola a una concatenazione (circolare). In una recente comunicazione, Clelia De Felice, Rosalba Zizza e Rocco Zaccagnino hanno individuato delle condizioni necessarie affinché un sistema splicing circolare finito di tipo (1,3) generi un linguaggio regolare e formulato una congettura sulle condizioni aggiuntive per caratterizzare tali sistemi che si intende studiare. Si intende inoltre continuare lo studio, della problematica legata alla buona codifica di problemi in sequenze di DNA, tematica centrale nel DNA Computing.Per quanto riguarda gli aspetti applicativi, si vuole proseguire lo studio della relazione tra l’operazione di splicing e la composizione musicale algoritmica. Inoltre, in collaborazione con Paola Bonizzoni, si prenderanno in esame possibili applicazioni della teoria degli automi alla bioinformatica. Infatti, il recente sviluppo di tecnologie Next Generation Sequencing in Bioinformatica ha stimolato l'applicazione di tecniche di teoria dei linguaggi dei formali e di indicizzazione di testi allo scopo di analizzare collezioni di sequenze molto simili tra loro.