Journal article · 2026 · Open access

Constructive S4 modal logics with the finite birelational frame property

Philippe Balbiani, Martín Diéguez, David Fernández–Duque, Brett McLean

Journal of the ACM · Published 10 October 2026 · DOI 10.1145/3857907

Open PDFView at the publisherCite this paper

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

All highly cited Computer Science papers

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.