Obbiettivo del progetto è lo sviluppo di ricerche basate sulla teoria dei linguaggi formali, degli automi e della complessità computazionale, con particolare interesse per i modelli e metodi probabilistici. Si possono rilevare due linee guida.
La prima riguarda l¿analisi di vari modelli computazionali, quali dispositivi a risorse limitate, in termini di proprietà combinatorie dei linguaggi associati. In particolare, nell¿ambito della quantum computing, si affronteranno sia problemi di decisione (decidere se un linguaggio riconosciuto da un automa quantistico è contenuto in un linguaggio regolare) che di sintesi ottima ( caratterizzare la sottoclasse di linguaggi regolari per cui l¿automa probabilistico minimo ha un numero di stati esponenzialmente più grande di quello quantistico). Si affronteranno inoltre problematiche relative ai linguaggi bidimensionali, ai linguaggi di parentesi (XML) e a problemi di algoritmi di base su dati compressi (con compressione grammaticale, su monoidi liberi o più in generale su monoidi finitamente presentati). Verranno infine sviluppate tecniche per il calcolo dello speed-up di monoidi parzialmente commutativi.
La seconda è ispirata a problemi interdisciplinari di carattere bioinformatico. Particolare attenzione sarà dedicata allo sviluppo e all¿analisi di algoritmi per l¿estrazione di informazioni per dati genomici o proteomici, con particolare riguardo a metodi per lo studio della stabilità dei cluster, attraverso tecniche basate su perturbazioni ottenute con proiezioni a caso. Verranno inoltre sviluppati modelli artificiali di dati genomici, da utilizzare come benchmark per confrontare sperimentalmente i vari algoritmi. Gli strumenti sviluppati nel corso della ricerca saranno validati con sperimentazioni sia su dati artificiali che naturali.