Algoritmi di riconoscimento di linguaggi traccia. I linguaggi traccia sono stati originariamente proposti in letteratura per lo studio della semantica di schemi di computazione concorrenti. Essi sono definiti a partire da un alfabeto finito e da una relazione commutazione tra suoi simboli che poi viene estesa tutte le parole e quindi ai relativi linguaggi. Le relative proprietà sono state studiate in letteratura innanzitutto come estensione della tradizionale teoria dei linguaggi formali e degli automi. La linea di ricerca specifica perseguita in questo ambito riguarda l’analisi di algoritmi per il riconoscimento di linguaggi traccia razionali. Questo tema è legato in modo naturale allo studio del parallelismo nei processi di compilazione. In alcuni casi si sono ottenuti algoritmi che risolvono il problema di riconoscimento per linguaggi traccia razionali in tempo lineare. Questi problemi sono naturalmente legati alle proprietà combinatorie e di enumerazione di tali linguaggi. (1992 - )

Complessità di problemi di clustering. Il classico problema di clustering consiste nel determinare una partizione di un insieme di punti in R^d che minimizzi la somma delle distanze degli stessi punti dai rispettivi centroidi. Procedure per la soluzione di questo problema sono alla base di molti metodi di apprendimento; esse trovano applicazioni in diversi ambiti di ricerca di informatica soprattutto dove occorre trattare una vasta mole di dati (bioinformatica, trattamento di immagini). La complessità del problema dipende da vari parametri: la dimensione dello spazio, il numero di insiemi della partizione, la norma assunta per determinare le distanze, eventuali ipotesi sui cluster della partizione. Il tema specifico affrontato in questo ambito riguarda lo studio della complessità del clustering assumendo vincoli di cardinalità sugli insiemi della partizione. Nella maggior parte dei casi il problema è NP-difficile, mentre in certe ipotesi esso è risolubile in tempo polinomiale e in questo caso è di interesse trovare l’algoritmo più efficiente. Gli obiettivi principali di questa linea di ricerca consistono proprio nel determinare le condizioni che rendono il problema difficile e quelle invece che consentono di trovare algoritmi efficienti. (2011 - )

Statistiche di pattern. L’obiettivo generale di questa linea di ricerca consiste nella valutazione probabilistica del numero di occorrenze di pattern in un testo generato a caso secondo un opportuno modello stocastico. L'argomento può essere incluso tra i problemi di conteggio e generazione casuale di parole in determinate famiglie di linguaggi formali. Questa problematica trova motivazioni e applicazioni in diversi ambiti di ricerca quali lo studio di modelli statistici per generare sequenze di DNA, l’analisi di algoritmi su stringhe, lo studio di vari problemi legati ai linguaggi formali e ai modelli di calcolo. I risultati principali riguardano le proprietà asintotiche di queste statistiche, al crescere della lunghezza del testo generato, tra le quali in particolare la loro distribuzione limite. Essi dipendono sia dai motivi (pattern) ricercati sia dal modello probabilistico assunto per la generazione casuale del testo. (2003 - )