I principali interessi di ricerca di Ugo Dal Lago riguardano l'informatica teorica e, in particolare, le possibili relazioni tra la teoria della complessità computazionale, la teoria della probabilità, la teoria dei linguaggi di programmazione e la logica matematica.
COMPUTAZIONE PROBABILISTICA ALL'ORDINE SUPERIORE
Nonostante l'algoritmo sia tradizionalmente considerato un processo deterministico, la possibilità di accedere ad una sorgente di casualità è stata presa in considerazione fin dagli albori dell'informatica teorica. Permettere agli algoritmi di evolvere in modo casuale risulta indispensabile in crittografia, mentre i modelli probabilistici sono alla base del machine learning. Tutta una serie di questioni rimangono tutt'ora aperte, nonostante la letteratura sull'argomento sia sconfinata. In particolare, l'impatto dell'adozione di un modello di calcolo probabilistico sulla teoria dei linguaggi di programmazione risulta largamente inesplorata, soprattutto in presenza di programmi all'ordine superiore.
SEMANTICA DIFFERENZIALE DEI LINGUAGGI DI PROGRAMMAZONE
La semantica dei linguaggi di programmazione è usualmente studiata tramite equivalenze e preordini su programmi, i quali non danno nessuna informazione di tipo quantitativo riguardo coppie di programmi tra loro non confrontabili. L'uso di metriche e pseudometriche, purché promettente, non permette di dare conto di differenze tra programmi che dipendano in modo determinante dal contesto. Si sta quindi cercando, attraverso nozioni di distanza tra programmi che non siano meramente numeriche, di riuscire a giustificare trasformazioni tra programmi che non siano corrette in tutti i contesti o che siano corrette solo in senso approssimato.
COMPLESSITA' COMPUTAZIONALE IMPLICITA
La complessità
computazionale implicita mira a dare caratterizzazioni di classi di
complessità basate sulla logica matematica. A partire dalla logica
lineare (introdotta da Girard quasi vent'anni fa) si possono definire
sistemi deduttivi cui corrispondono classi di complessità, non appena
l'eliminazione del taglio è interpretata come meccanismo di
computazione. In particolare, caratterizzazioni del tempo polinomiale
(deterministico o nondeterministico) e del tempo elementare sono state
introdotte da Girard, Lafont e altri ricercatori. Tali proposte
risultano interessanti sia dal punto di vista della complessità
computazionale, sia nel senso dei linguaggi di programmazione, visto
che i sistemi proposti corrispondono (nel senso della corrispondenza di
Curry-Howard) a linguaggi paradigmatici di programmazione.
