Course

References

Lecture Notes

Problem Sets

References

Recommended Reading

• Complementation of Büchi automata: Orna Kupferman and Moshe Y. Vardi, Weak alternating automata are not that weak, ACM Transactions on Computational Logic

• Safra’s Construction: Madhavan Mukund, Finite-state automata on infinite inputs, Tutorial talk, August 1996, TCS-96-2.

• Strongly Connected Components: Cormen, Leiserson, Rivest: Introduction to Algorithms

• Alternating Automata and LTL: Moshe Vardi, Alternating automata and program verification, LNCS Vol. 1000

• Parity Games: Wieslaw Zielonka, Infinite games on finitely coloured graphs with applications to automata on infinite trees, Theoretical Computer Science, Volume 200, Issues 1-2, 28 June 1998, Pages 135-183.

• Solving Parity Games: Marcin Jurdziński, Small Progress Measures for Solving Parity Games STACS 2000, February 2000

• The Complementation Problem for Automata on Infinite Trees: Wolfgang Thomas, Languages, Automata, and Logic, 1997.