BISIMULATIONS AND FILTRATIONS IN MODAL LOGIC Valentin Shehtman, Ilya Shapirovsky
31ST EUROPEAN SUMMER SCHOOL IN LOGIC, LANGUAGE AND INFORMATION, August 5-9, 2019
Lecture 1 (Shehtman) Finite model property and decidability (Harrop’s theorem). The method of filtrations; examples: the finite model property of K, KB, K4. General notion of filtration of a Kripke model. Locally tabular (locally finite) logics and hereditary finite model property; example: logic S5.
Slides
Lecture 2 (Shapirovsky) Logics that admit filtration. Filtration safe operations on frames and logics. Enriching modal language with the converse and the transitive closure modality. Strict inclusions between classes of Kripke complete logics, logics with the finite model property, logics that admit filtration, and locally finite logics.
Slides
Lecture 3 (Shehtman) Bisimulations. Van Benthem’s theorem. Bisimulation games. Fine’s theorem on normal forms. Game stabilization and finite modal depth. Local finiteness of logics of finite modal depth. Segerberg-Maksimova criterion of local finiteness above K4.
Slides
Lecture 4 (Shapirovsky) Partitions, filtrations, and local finiteness. Combinatorial criteria of local finiteness. Examples: logics K5 and the difference logic. Generalizations of Segerberg-Maksimova criterion of local finiteness in the non-transitive case.
Slides
Lecture 5 (Shehtman/Shapirovsky) Further results and open questions.
Slides, Part I (Shehtman) Slides, Part II (Shapirovsky)
For prerequisites, see:
- Blackburn, P., de Rijke, M., Venema, Y. Modal Logic, Cambridge Tracts in Theoretical Computer Science, vol. 53. Cambridge University Press (2002), Chapters 1,2
- Goldblatt, R. Logics of Time and Computation, Center for the Study of Language and Information, 1992. Chapters 3,4
- Chagrov, A. and M. Zakharyaschev, Modal Logic, Oxford Logic Guides 35, Oxford University Press, 1997, Chapter 12
|