Mikołaj Bojańczyk > Automaty a Logika (wykład 2013/2014)


Automata and Logic

Exam questions (Polish)

Tutorials


Past lectures

Part I. Equivalence of automata and monadic second-order logic (current version of slides)

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.


Part II. Logics weaker than monadic second-order logic (current version of slides)

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


Part III. Trees in disguise

Tree-width and clique-width. The Courcelle theorem.

The Guarded Fragment


Reading material

Languages, automata and logic by Wolfgang Thomas

Students' notes from my 2009 lecture (in Polish)