Profesor: Pablo Barceló, IMC
Fecha: del 5 al 7 de Enero 2021
Hora: de 11:00 a 12:00 hrs
En este mini-curso daremos una mirada a algunas importantes aplicaciones de lógica en ciencia de la computación. Comenzaremos con un breve repaso de la lógica de primer orden, para luego estudiar su poder expresivo sobre la clase de palabras sobre alfabetos finitos. Demostraremos en ese contexto que la lógica de primer orden no es capaz de expresar todos los lenguajes regulares y propondremos una extensión de ésta, basada en cuantificadores monádicos de segundo orden, que sí lo logra. Luego de eso estudiaremos la capacidad que tiene la lógica de primer orden para extraer información relevante desde bases de datos relacionales, y demostraremos un límite importante en su capacidad expresiva relacionada con la carencia de recursión. Para subsanar esta deficiencia mostraremos lógicas con capacidades recursivas que son capaces de expresar todas las propiedades que se pueden evaluar en tiempo polinomial.