Journal article · 2026 · Open access
Constructive S4 modal logics with the finite birelational frame property
Journal of the ACM · Published 10 October 2026 · DOI 10.1145/3857907
In brief
“Constructive S4 modal logics with the finite birelational frame property” is a 2026 journal article by Philippe Balbiani and 3 co-authors, published in Journal of the ACM. OpenAlex counts 4 citations as of 17 November 2026. It is open access under a CC BY licence: the full text is free to read at Journal of the ACM.
- Citations
- 4
- Most cited in
- 2026 (3)
- Field-weighted impact
- 7.12
- References
- 39
- Authors
- 4
Abstract
The logics \(\mathsf {CS4} \) and \(\mathsf {IS4} \) are the two leading intuitionistic variants of the modal logic \(\mathsf {S4} \) . Whether the finite model property holds for each of these logics have been long-standing open problems. In this paper, we resolve the first of these problems, proving that \(\mathsf {CS4} \) has the finite frame property. Additionally, we investigate the following three logics closely related to \(\mathsf {IS4} \) . The logic \(\mathsf {GS4} \) is obtained by adding the Gödel–Dummett axiom to \(\mathsf {IS4} \) ; it is both a superintuitionistic and a fuzzy logic and has previously been given a real-valued semantics. We provide an alternative birelational semantics and prove strong completeness with respect to this semantics. The extension \(\mathsf {GS4}^c \) of \(\mathsf {GS4} \) corresponds to requiring a crisp accessibility relation on the real-valued semantics. We give \(\mathsf {GS4}^c \) a birelational semantics corresponding to an extra confluence condition on the \(\mathsf {GS4} \) birelational semantics and prove strong completeness. Neither of these two logics have the finite model property with respect to their real-valued semantics, but we prove that they have the finite frame property with respect to their birelational semantics. Establishing the finite birelational frame property immediately establishes decidability, which was previously open for these two logics. Our proofs yield coNEXPTIME upper bounds for \(\mathsf {CS4} \) , \(\mathsf {GS4} \) , and \(\mathsf {GS4}^c \) . The logic \(\mathsf {S4I} \) is obtained from \(\mathsf {IS4} \) by reversing the roles of the modal and intuitionistic relations in the birelational semantics. We also prove the finite frame property, and thereby decidability, for \(\mathsf {S4I} \) , although our proof does not yield an elementary complexity bound. In summary, we prove that \(\mathsf {CS4} \) , \(\mathsf {GS4} \) , \(\mathsf {GS4}^c \) , and \(\mathsf {S4I} \) all have the finite birelational frame property, with the first three having a coNEXPTIME validity problem.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Balbiani, P., Diéguez, M., Fernández–Duque, D., & McLean, B. (2026). Constructive S4 modal logics with the finite birelational frame property. Journal of the ACM. https://doi.org/10.1145/3857907
MLA 9
Balbiani, Philippe, et al. “Constructive S4 modal logics with the finite birelational frame property.” Journal of the ACM, 2026. https://doi.org/10.1145/3857907.
Chicago
Balbiani, Philippe, Martín Diéguez, David Fernández–Duque, and Brett McLean. 2026. “Constructive S4 modal logics with the finite birelational frame property.” Journal of the ACM. https://doi.org/10.1145/3857907.
Harvard
Balbiani, P. et al. (2026) ‘Constructive S4 modal logics with the finite birelational frame property’, Journal of the ACM. doi:10.1145/3857907.
IEEE
P. Balbiani, M. Diéguez, D. Fernández–Duque, and B. McLean, “Constructive S4 modal logics with the finite birelational frame property,” Journal of the ACM, 2026, doi: 10.1145/3857907.
BibTeX
@article{balbiani2026constructive,
title = {{Constructive S4 modal logics with the finite birelational frame property}},
author = {Balbiani, Philippe and Diéguez, Martín and Fernández–Duque, David and McLean, Brett},
journal = {Journal of the ACM},
year = {2026},
doi = {10.1145/3857907},
url = {https://doi.org/10.1145/3857907}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Topic and keywords
Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Algebra and Logic
- finite model property
- fuzzy logic
- superintuitionistic logics
- strong completeness
- decidability
- accessibility relations
Work with this paper
Most-cited papers in Computer Science
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
Questions about this paper
How do I cite this paper in APA style?
Balbiani, P., Diéguez, M., Fernández–Duque, D., & McLean, B. (2026). Constructive S4 modal logics with the finite birelational frame property. Journal of the ACM. https://doi.org/10.1145/3857907
How many times has this paper been cited?
4 times, according to OpenAlex on 17 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.
Is this paper free to read?
Yes. It is open access at Journal of the ACM: sign in and open the PDF from this page.
Who wrote this paper?
Philippe Balbiani, Martín Diéguez, David Fernández–Duque, Brett McLean.
What is the DOI of this paper?
10.1145/3857907, permanently at https://doi.org/10.1145/3857907. Sign in and open it from this page.
Bibliographic data from OpenAlex (CC0), last checked 17 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.