Computación Paralela y Eliminación de Cuantificadores

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.