Research Group on Natural Computing

Speaker:
Prof. Jörg Flum
Abteilung für mathematische Logik
(Departamento de Lógica Matemática)
Albert-Ludwigs-Universität Freiburg (Alemania)

Title: Computación paralela y eliminación de cuantificadores

Abstract:
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. Presentaremos una caracterización de las clases K con esta propiedad y veremos 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.

Information:

• Date: Monday, November 12th
• Time: 10:00.
• Place: Seminario I del Instituto de Matemáticas Universidad de Sevilla
• Language: Spanish

Organized by: Research Group on Natural Computing
Instituto de Matemáticas Universidad de Sevilla Antonio de Castro Brzezicki
Red Temática Española en Computación Biomolecular y Biocelular