Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Misurazione della Complessita' e introduzione alla classe P. La classe dei problemi NP. Problemi NP-Completi.
* CAL - Calcolabilita'
Problemi decidibili e indecidibili. Mapping Reducibility. Linear Bounded Automata e Post Correspondence Problem. Decidibilita' delle teorie logiche.
* CAL - Calcolabilita'
Introduzione alle Macchine di Turing. Macchine di Turing multinastro. Macchine di Turing nondeterministiche. Macchine di Turing Universali.
* ALF - Automi e Linguaggi Formali
Breve introduzione al corso. Automi deterministici e nondeterministici. Proprieta' di chiusura. Automi Pushdown con relative proprieta' di chiusura.
COM - Complessita'
Space Complexity. Savitch's Theorem e la classe PSPACE. PSPACE-completeness.
COM - Complessita'
Le classi EXPTIME e EXPSPACE e loro completezza.
* ALF - Automi e Linguaggi Formali
Introduzione agli automi nondeterministici su parole infinite. Espressioni omega-regolari. Proprieta' di chiusura, di proiezione, di determinizzazione, di inclusione e di complementazione.
* ALF - Automi e Linguaggi Formali
Introduzione agli automi alternanti. Il problema del vuoto. Algoritmi per la risoluzione del problema del vuoto per automi nondeterministici e alternanti
L - Logica
Introduzione alle logiche temporali lineari. Problemi decisionali per LTL. Confronto tra i poteri espressivi di LTL, QLTL e delle espressioni omega-regolari.