Mikołaj Bojańczyk > Automaty a Logika (wykład 2013/2014)
Exam questions (Polish)
October 4. Monadic second-order logic on finite words. Introduction to Büchi automata
October 18. Complementation of Büchi automata, and therefore their equivalence to monadic second-order logic.
October 25. From nondeterministic Büchi to deterministic Muller.
November 8. Beginning of Rabin's tree theorem: automata on infinite trees.
November 15. Positional determinacy of parity games.
November 23. End of Rabin's theorem: alternating automata. Strictness of the alternating hierarchy.
November 30. Weak monadic second-order logic.
Coming lectures (lines are not necessarily equal to lectures)
First-order logic, linear temporal logic, and their equivalence via aperiodic monoids
Temporal logics on trees
Tree-width and clique-width. The Courcelle theorem.
The Guarded Fragment
Languages, automata and logic by Wolfgang Thomas
Students' notes from my 2009 lecture (in Polish)