Girlando, M., Kuznets, R., Marin, S., Morales, M., & Straßburger, L. (2023). Intuitionistic S4 is decidable. In 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). LICS 2023: Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science, Boston, MA, United States of America (the). IEEE. https://doi.org/10.34726/5295
In this paper we demonstrate decidability for the intuitionistic modal logic S4 first formulated by Fischer Servi. This solves a problem that has been open for almost thirty years since it had been posed in Simpson's PhD thesis in 1994. We obtain this result by performing proof search in a labelled deductive system that, instead of using only one binary relation on the labels, employs two: one corresponding to the accessibility relation of modal logic and the other corresponding to the order relation of intuitionistic Kripke frames. Our search algorithm outputs either a proof or a finite counter-model, thus, additionally establishing the finite model property for intuitionistic S4, which has been another long-standing open problem in the area.
en
Project title:
Reasoning about Knowledge in Byzantine Distributed Systems: P 33600-N (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
-
Project (external):
Horizon 2021 programme, under the Marie Skłodowska-Curie grant CYDER
CC BY 4.0
