Research | Funded Projects

LINGUAGGI FORMALI E CODICI: METODI COMBINATORI E ORIENTAMENTI APPLICATIVI

Saranno sviluppate le seguenti linee di ricerca: 1. I codici comma-free sono insiemi di stringhe in cui nessuna stringa è fattore di una concatenazione delle altre. Essi rientrano nella famiglia dei codici circolari. I codici cross-bifix-free di stringhe sono insiemi di stringhe di lunghezza fissata tali che nessun prefisso di una stringa dell’insieme è anche suffisso di una stringa dell’insieme. In altri termini non è possibile accavallare due stringhe del codice. Le proprietà di questi codici sono utilizzate nella sincronizzazione dei messaggi. Si intendono studiare le generalizzazioni a due dimensioni di tali codici. L’estensione in due dimensioni di codice circolare implica l’introduzione del concetto di tiling su strutture tri-dimensionali più complesse, come il cilindro o il toroide. In analogia al caso delle stringhe, si vuole mettere in relazione la proprietà di univoca decifrabilità con una opportuna definizione di relazione di coniugio fra picture. Particolare importanza rivestono i codici cross-bifix-free non-estendibili, ovvero massimali all’interno dell’insieme delle picture della taglia fissata, che hanno una cardinalità elevata. L’introduzione di questi codici implica inoltre lo studio degli accavallamenti fra picture e dei loro bordi. In particolare gli accavallamenti di una picture con sé stessa sono correlati alla periodicità della picture. Lo studio della periodicità di una picture gioca un ruolo importante nei problemi di pattern matching bidimensionale. 2. 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 (Fraenkel e Simpson) che il numero di tali fattori sia al più n ed esaminare l’analogo problema per le parole circolari. 3. Una parola di Lyndon è una parola primitiva minimale nella sua classe di coniugazione, rispetto all’ordine lessicografico, e ogni stringa ha un’unica speciale fattorizzazione in prodotto di tali parole. Si intendono studiare le potenzialità della fattorizzazione di Lyndon e sue varianti, allo scopo di rappresentare e analizzare l’informazione molecolare efficientemente, migliorando i risultati già esistenti dal punto di vista algoritmico in bioinformatica. 4. Un codice X prefisso massimale e razionale (cioè riconosciuto da un automa finito) può, in alcuni casi, essere ottenuto da un codice più semplice, ancora prefisso massimale e razionale, mediante l’operazione di decomposizione. In un recente lavoro viene presentata una procedura, basata sull’automa minimale di X, che stabilisce quando questo sia possibile e, in tal caso, costruisce codici razionali su cui X si decompone. La “state complexity” di un linguaggio regolare è il numero degli stati nell’automa (deterministico) minimale completo che riconosce il linguaggio. Si intendono studiare le state complexity dei fattori su cui X si decompone mediante la suddetta procedura, confrontandole con quella di X. 5. Si intende studiare la congettura della fattorizzazione per alcune famiglie di codici massimali finiti. 6. 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. Un argomento di questa ricerca sarà stabilire se tali condizioni siano anche necessarie o se restino sufficienti per altre famiglie di sistemi. Si intende studiare una procedura che consente 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 and Rozenberg (1983), connesso a tale problematica. 7. Per quanto riguarda altri aspetti applicativi, si vuole proseguire lo studio della relazione tra l’operazione di splicing e la composizione musicale algoritmica.