NAIL140 Selected topics in logic

Seminar for students interested in logic and its applications in computer science.

About this course

This is a referative seminar aimed at broadening and deepening knowledge in the field of logic and its applications in computer science. The seminar does not follow a fixed syllabus; the current topic is selected with regard to the participants’ interests and developments in the field. The course is suitable for master’s and doctoral students. Repeated enrollment is possible.

Credit will be awarded for active participation in the seminar, including a presentation of assigned material.

The course is suitable for Bachelor students and above, no prerequisities are required beyond interest in logic and knowledge of the basics (e.g. the course NAIL062 P&P Logic).

If you are interested, please enroll in the SIS, or contact me or Petr Gregor with any questions.

• NAIL140 in the SIS

The topics will be discussed at the beginning of the semester.

Spring 2026

• Monday 2pm in S303 (starting from the 2nd week of the semester)

Topic and resources

We wil cover descriptive complexity, Fagin’s theorem, and fixed-point logics.

Main resource:

• Grädel, E. (2007). Finite Model Theory and Descriptive Complexity. In: Finite Model Theory and Its Applications (pp. 125–230). Springer. https://doi.org/10.1007/3-540-68804-8_3

Supplementary resources:

• Sipser, M. (with Lee, M.). (2013). Introduction to the theory of computation (3rd ed.). Course Technology Cengage Learning.

Program

• Week 1: Introduction, discussion of possible topics.
• Week 2: The Hintikka Model checking game, strategy problem for finite games, equivalence with Horn-SAT. [Grädel 3.1.1-3.1.4]
• Week 3: Basics of complexity theory, Alternating Turing Machines, Complexity of FO Model checking. [Grädel 3.1.4]
• Week 4: APTIME=PSPACE, ALOGSPACE=PTIME, QBF is NP-complete. Encoding structures by words [Grädel part of 3.1.5, Sipser 10.3, 8.3]
• Week 5: The canonical encoding is good. Isomorphism invariance, its undecidability using Trakhtenbrot’s theorem. [Grädel the rest of 3.1.5]
• Week 6: Generalized spectrum, example: Hamiltonian circuit. Fagin’s theorem: the easy implication. [Grädel 3.2.1]
• Week 7: PLAN: Fagin’s theorem: the hard implication.
• Week 8:
• Week 9:
• Week 10:
• Week 11: