Reading Course on Automata and Logic

The course will be based on reading several published papers, and on this draft of course notes .

There will be an introductory meeting

Wednesday, January 20

• Meeting 1 Modal Logic

  Time: Thursday, January 28, 13:00 - 15:00

  Readings:

  • Chapter 4 of the lecture notes (which refers to the earlier introductory chapters).
  • Moshe Vardi, Why is Modal Logic so Robustly Decidable? In Descriptive Complexity and Finite Models, Proceedings of a DIMACS Workshop 1996 Princeton, New Jersey, USA, January 14-17, 1996. Online version
    Section 4 of the paper (concerning fixpoint logics) is not important at this point in the course, and Section 3 is not essential either.

• Meeting 2 The Guarded Fragment of First-order Logic

  Time: Thursday, February 11, 12:00 - 14:00

  Readings:

  • Chapter 5 of the lecture notes (which refers to the earlier introductory chapters).
  • Erich Grädel Decision procedures for guarded logics. In Automated Deduction . CADE16. Proceedings of 16th International Conference on Automated Deduction, Trento, 1999, vol. 1632 of LNCS. Springer, 1999 Online version
  • Christoph Löding Infinite Tree Automata Online Version

• Meeting 3, The Guarded Negation Fragment of First-order Logic

  Time: Thursday, February 25, 12:00 - 14:00

  Readings:

  • Vince Barany, Balder ten Cate, Luc Segoufin Guarded Negation. In Journal of the ACM, Volume 62, Issue 3, 2015 Online version
  • Chapter 6 of the lecture notes.

• Meeting 4

  Time: Thursday, March 11, 12:00 - 14:00

  Topic TBD depending on progress in prior weeks.

For MFoCS students the course is examined via mini-project.