Giochi di Ehrenfeucht-Fraissé complessità computazionale e applicazioni
Durata: 28 ore
Programma
Modulo 1 (14 ore) - Prof. Angelo Montanari
Modulo 2 (14 ore) - Prof. Nicola Vitacolonna
PROGRAMMA:
Per avere un'idea dei contenuti si
può far riferimento ai lucidi di un corso tenuto a ESSLLI 2010
disponibili sulla mia pagina web all'indirizzo:
http://sole.dimi.uniud.it/~angelo.montanari/courses.php
strutturato in 5 blocchi:
Lesson 1: Introduction to EF-games
Lesson 2: Inexpressivity results for first-order logic
Lesson 3: Normal forms for first-order logic
Lesson 4: Algorithms and complexity for specific classes of structures
Lesson 5: General complexity bounds
Sicuramente, contiamo di espandere le parti di base per
fornire agli studenti tutte le conoscenze di base necessarie
per comprendere i contenuti del corso.
