instituto de matemáticas universidad de sevilla
Antonio de Castro Brzezicki
imus-logo
Computación Paralela y Eliminación de Cuantificadores
Conferencias
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.
 

Compártelo: