Ciclo de Charlas del IMASL
Introducción a la Complejidad Descriptiva

El martes 9 de noviembre a las 11 horas se realizará en el aula 54 del Bloque II de la Facultad de Ciencias Físico Matemáticas y Naturales una nueva charla organizada por el Instituto de Matemática Aplicada San Luis (IMASL) sobre "Introducción a la Complejidad Descriptiva " a cargo del Dr. José M. Turull Torres de la School of Engineering and Advanced Techonology de la Massey University , Nueva Zalanda.

Esta conferencia está dirigida a estudiantes de posgrado de las disciplinas en ciencias Matemática, Computación y Física, de interés para estudiantes de Informática y público en general.

Resumen de la disertación

¿Qué tan poderoso debe ser un lenguaje para que podamos expresar en él una determinada propiedad en la clase de estructuras finitas de un cierto vocabulario (o tipo) relacional?. Por ejemplo, en la clase de grafos, puede expresarse la propiedad de conectividad en un lenguaje lógico de primer orden.

En la disertación se dará una breve introducción a algunas lógicas y  ejemplos de propiedades en la clase de grafos finitos que son expresables en esas lógicas, y de otras que no lo son.

Los juegos de Ehrenfeucht-Fraissee proveen una caracterización algebraica del poder de discernimiento de una lógica dada con respecto a dos estructuras dadas, y constituyen uno de los métodos más importantes en la Complejidad Descriptiva para probar la indefinibilidad de ciertas propiedades en ciertas lógicas.

Se verá brevemente en que consisten estos juegos para el caso de la lógica de primer orden y para la lógica infinitaria con cantidad finita de variables, así como algunos ejemplos simples de su uso.