Research | Funded Projects

CODICI E SISTEMI SPLICING NELLA TEORIA DEI LINGUAGGI FORMALI

La ricerca riguarderà alcuni aspetti della teoria dei codici a lunghezza variabile e i sistemi splicing circolari finiti.Per quanto riguarda i codici 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 regolare (cioè riconosciuto da un automa finito) può, in alcuni casi, essere ottenuto da un codice massimale prefisso finito, mediante l’operazione di decomposizione. S’intende stabilire se tale proprietà sia decidibile. Un problema successivo sarà caratterizzare i codici di tale famiglia.2. Estensione della teoria dei codici al caso bidimensionale.Questa ricerca continua quella iniziata nel lavoro [Marcella Anselmo, Dora Giammarresi, Maria Madonia: Two Dimensional Prefix Codes of Pictures. Developments in Language Theory 2013: 46-57] dove è stato dimostrato che la proprietà di essere un codice è indecidibile per i linguaggi bidimensionali anche finiti. Da qui sorge quindi la necessità di interessarsi a sottofamiglie di codici per le quali l’appartenenza di un linguaggio diventa decidibile, come quella dei codici prefissi, o, più in generale, a ritardo di decifrazione finito. S’intende proseguire lo studio di sottofamiglie di codici bidimensionali per le quali sia ugualmente decidibile stabilirne l’appartenenza, seguendo le linee tracciate dalla teoria dei codici di stringhe. In particolare 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. Inoltre ci si propone di valutare la misura dei codici bidimensionali, al fine di estendere la ben nota diseguaglianza di Kraft-McMillan per i codici di stringhe.3. Studio delle relazioni tra codici prefissi e bifissi, combinatoria delle parole e teoria dei gruppi, continuando uno studio già intrapreso in vari lavori accettati per pubblicazione o sottomessi (si veda ad esempio [Valérie Berthé, Clelia De Felice, Francesco Dolce, Julien Leroy, Dominique Perrin, Christophe Reutenauer, The finite index basis property, accettato per pubblicazione in J. of Pure and Appl. Alg.; Valérie Berthé, Clelia De Felice, Francesco Dolce, Julien Leroy, Dominique Perrin, Christophe Reutenauer, Bifix codes and interval exchanges, accettato per pubblicazione in J. of Pure and Appl. Alg.]).4. Congettura della fattorizzazione e caratterizzazione della struttura dei codici che la verificano.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 nel lavoro [Clelia De Felice: A note on the factorization conjecture, Acta Informatica 50 (7-8): 381-402 (2013)].Per quanto riguarda i sistemi splicing circolari finiti, alcuni partecipanti a questa ricerca hanno individuato delle condizioni necessarie affinché un sistema splicing circolare finito di tipo (1,3) generi un linguaggio regolare [Clelia De Felice, Rocco Zaccagnino, Rosalba Zizza, Unavoidable Sets and Regularity of Languages Generated by (1,3)-Circular Splicing Systems, sottomesso per pubblicazione]. Inoltre per la sottoclasse dei sistemi ibridi hanno formulato una congettura sulla caratterizzazione dei sistemi in tale sottoclasse che generano linguaggi regolari. S’intende studiare tale congettura sui sistemi ibridi.