Reading group on Automata, Logics, and Infinite Games
We are reading the book Automata, Logics, and Infinite Games: A guide to current research by Erich Grädel, Wolfgang Thomas, and Thomas Wilke.The book is available for download as PDFs from here if you access the page via the university library's web proxy.
We have bi-weekly meetings, which are subject to sceduling. For each meeting, everyone reads the relevant part of the book before each meeting, but each meeting will also have a facilitator who will briefly summarize the contents of the chapter and then lead some discussion or present some exercises from the book that we do together etc. The facilitator gets to decide the structure of the meeting as they find fitting. We'll change who is the facilitator in a round-robin schedule where everyone gets an even share of this responsibility.
(Note: Being a facilitator does not mean that you have to deliver any type of lecture and does not mean that you have to understand the topics better than others. It's simply the person who structures the meeting if necessary.)
For attending this course, it will be useful to have some basic background on theory of computation, logic, and proofs.
This reading group welcomes people from all levels of education that are eager to learn about the topic. PhD students can take this as an official course offering 3 credits. For PhD students officaly registered to the course, it is necessary to present at least one or more chapters based on the estimated load.
Additional literature:
The following books offer suplementary material in several topics, which are available for "deep dives", depending on interest.- L. Libkin: Elements of Finite Model Theory, Springer-Verlag, Texts in Theoretical Computer Science, 2004.
A great textbook for suplementing the material in general and learing more on Ehrenfeucht-Fraïssé Games and how they help in learning the expressive power of a logic, other kinds of logics, and more information on the role of Turing machines. This book is available for download as PDFs from here.
- M. Huth and M.D. Ryan: Logic in Computer Science – Modelling and Reasoning about Systems, Cambridge University Press, 2nd edition, 2004.
This is great book for an introduction to natural deduction and how it can be used to help us reason about programs. This book is available for download as PDFs from here.
- N. Immerman: Descriptive Complexity, Springer Graduate Texts in Computer Science, 1999.
The science of descriptive complexity studies systematicaly how the expressive power of various logics affects the necessary computational power for solving their satisfiability. This book provides and overview of the most interesting results in the interplay between logic, expresivity, and complexity. The book is available for download as a PDF here.
Schedule:
| When | What | Who |
|---|---|---|
| 29 - 9 - 2023 | Introduction to the course, notation, and preliminaries. | Elli |
| 20 - 10 - 2023 | Chapter 1: Omega-Automata | Hooman |
| 3 - 11 - 2023 | Chapter 2: Infinite Games | Stephan | 10 - 11 - 2023 | Chapter 3: Determinization of Büchi-Automata | Nick | 24 - 11 - 2023 | Chapter 4: Complementation of Büchi Automata Using Alternation | Tobias | 1 - 12 - 2023 | Chapter 6: Memoryless Determinacy of Parity Games | Sarbojit | 26 - 1 - 2024 | Chapter 9: Alternating Tree Automata | Fredrik | 16 - 2 - 2024 | Chapters 10-11: Modal μ-Calculus | Elli | 1 - 3 - 2024 | Chapter 14: Expressive Power of MSO and Modal μ-Calculus | Samuel |