Logic and Computation II
Based on the subjects we learned in the previous semester (1. computable functions; 2. complexity theory; 3. first-order logic), we will move on to more advanced topics on modal logic, infinite automata, desciriptive set theory, etc.
Lecturer
Date
4th March ~ 29th May, 2025
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Tuesday,Thursday | 15:20 - 16:55 | A3-2-301 | ZOOM 09 | 230 432 7880 | BIMSA |
Prerequisite
"Logic and Computation I" or equivalent knowledge of mathematical logic and theory of computation.
Syllabus
4. Modal logic
Kripke models, Kripke-complete and canonical logics, standard translation, bisimulation, decidability results, and epistemic logic.
5. Mu-calculus
Second-order logic, inductive operators, Modal mu-calculus and game semantics, alternation hierarcy, applications to temporal logics.
6. Automata on infite objects
Buechi automata and S1S, tree automata and S2S, finite model theory and parity games.
7. Recursion-theoretic hierarchies
Oracle computation, m-degrees and T-degrees, arithmetical and analytical hierarchies,
descriptive set theory.
"Logic and Computation III" will cover further advanced topics related to second-order arithmetic and admissible set theory.
Kripke models, Kripke-complete and canonical logics, standard translation, bisimulation, decidability results, and epistemic logic.
5. Mu-calculus
Second-order logic, inductive operators, Modal mu-calculus and game semantics, alternation hierarcy, applications to temporal logics.
6. Automata on infite objects
Buechi automata and S1S, tree automata and S2S, finite model theory and parity games.
7. Recursion-theoretic hierarchies
Oracle computation, m-degrees and T-degrees, arithmetical and analytical hierarchies,
descriptive set theory.
"Logic and Computation III" will cover further advanced topics related to second-order arithmetic and admissible set theory.
Reference
[1] H.D. Ebbinghaus, H. Flum and W. Thomas, Mathematical Logic, 3rd ed., Springer 2021.
[2] D.C. Kozen, Theory of Computation, Springer 2006.
[3] P. Blackburn, M. de Rijke and Y. Venema, Modal Logic, Cambridge UP, 2002.
[4] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.
[2] D.C. Kozen, Theory of Computation, Springer 2006.
[3] P. Blackburn, M. de Rijke and Y. Venema, Modal Logic, Cambridge UP, 2002.
[4] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.
Audience
Advanced Undergraduate
, Graduate
Video Public
No
Notes Public
Yes
Language
English
Lecturer Intro
Kazuyuki Tanaka received his Ph.D. from U.C. Berkeley. Before joining BIMSA in 2022, he taught at Tokyo Inst. Tech and Tohoku University, and supervised fifteen Ph.D. students. He is most known for his works on second-order arithmetic and reverse mathematics, e.g., Tanaka's embedding theorem for WKLo and the Tanaka formulas for conservation results. For more details: https://sendailogic.com/tanaka.html