Organizer
Mario de Jesús Pérez Jiménez
Lugar
Seminario I (IMUS), Edificio Celestino Mutis
Tipo de evento
Descripción
Decimos que una clase K de grafos permite la eliminación generalizada de cuantificadores, si para cierto número natural q, cada propiedad definible en el lenguaje de primer orden ya es definible por una fórmula de rango cuantificatorial menor que q. En esta charla se presentará una caracterización de las clases K con esta propiedad y se justificará que coinciden con las clases para las cuales fórmulas del lenguaje de primer orden pueden ser evaluadas en paralelo por circuitos booleanos de profundidad acotada.La conferencia será impartida en español.
