Research | Funded Projects

CODICI, COMBINATORIA DELLE PAROLE E LINGUAGGI FORMALI: ASPETTI TEORICI E ORIENTAMENTI APPLICATIVI

Saranno sviluppate le seguenti linee di ricerca: 1.Una linea di ricerca tratterà la generalizzazione dei codici di stringhe al caso bidimensionale dei codici di picture. L’interesse è stato finora rivolto principalmente al caso dei codici finiti e solo qualche esempio di codice di cardinalità infinita è stato considerato. Si intende trattare il caso dei codici di picture riconoscibili tramite tiling system per poterne studiare le proprietà combinatorie e strutturali e poter approfondire problemi di decidibilità anche nel caso di codici di cardinalità infinita. Nell’ottica poi di poter considerare soluzioni algoritmiche a problemi sui codici bidimensionali, si prevede di introdurre delle strutture dati che permettano di implementare efficientemente le decomposizioni di una picture con picture prese da un dato insieme o codice. Si noti che in letteratura il problema della codifica delle immagini è stato generalmente affrontato linearizzando le immagini e riconducendosi così a problemi su stringhe. Tale approccio ignora la natura bidimensionale delle picture. Si intende esaminare il problema della codifica e decodifica di picture usando picture di taglia variabile. 2.Negli ultimi mesi, alcuni partecipanti a questo progetto hanno proposto una variante della definizione di parola di Lyndon e della fattorizzazione di Lyndon, allo scopo di migliorarne l’applicazione ad alcuni problemi di bioinformatica. Si prevede di proseguire lo studio delle potenzialità della fattorizzazione di Lyndon e della sua summenzionata variante. Precisamente sarà studiata la possibilità di definire algoritmi di compressione e di costruzione del suffix array associato a una sequenza molecolare, utilizzando le suddette fattorizzazioni. L'efficienza di tali eventuali algoritmi sarà successivamente confrontata con quella degli algoritmi esistenti in letteratura.3.Per quanto riguarda i sistemi splicing circolari finiti, in un recente articolo sono state individuate delle condizioni sufficienti affinché un sistema splicing circolare di tipo (1,3) generi un linguaggio regolare. Si vuole stabilire se tali condizioni siano anche necessarie o se restino sufficienti per altre famiglie di sistemi. Ci si propone di studiare una procedura che consenta di decidere l'inevitabilità di un linguaggio attraverso un grafo a esso associato (Lothaire, 2002), al fine di produrre una prova alternativa a un risultato di Ehrenfeucht, Haussler e Rozenberg (1983), connesso a tale problematica.4.Per quanto riguarda la connessione tra codici, combinatoria delle parole e gruppi liberi, sarà affrontato lo studio dei codici massimali negli insiemi fattoriali, generalizzando i risultati già ottenuti per i codici biprefissi massimali.5.Si vuole studiare la congettura della fattorizzazione per alcune famiglie di codici massimali finiti. Saranno approfondite alcune relazioni tra i codici che verificano la congettura della fattorizzazione e le fattorizzazioni dei gruppi ciclici, messe in evidenza in un articolo non ancora pubblicato (Clelia De Felice, Some conjectures on codes, 2016, https://arxiv.org/abs/1611.04580).6.Fornire un limite superiore al numero dei quadrati distinti, cioè dei fattori della forma xx, in una parola di lunghezza n, è un problema studiato da diversi autori e ha relazioni con il problema del pattern matching. Si intende studiare la congettura di Fraenkel e Simpson, secondo la quale il numero di tali fattori è al più n. Ci si propone di esaminare l’analogo problema per le parole circolari, sul quale non sono noti risultati o congetture.