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)*