The Topological Mu-Calculus: Completeness and Decidability

被引：0
作者：
Baltag, Alexandru [1 ]
Bezhanishvili, Nick [1 ]
Fernandez-Duque, David [2 ]
机构：
[1] Univ Amsterdam, Inst Log Language & Computat, Sci Pk 107, NL-1090 GE Amsterdam, Netherlands
[2] Univ Barcelona, Dept Philosophy, C Montalegre 6-8, Barcelona 08003, Spain
来源：
JOURNAL OF THE ACM | 2023年 / 70卷 / 05期
关键词：
Fixpoint logic; topological semantics; completeness; decidability; LOGICS; MODEL;
D O I：
10.1145/3623268
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We study the topological mu-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability, and finite model property over general topological spaces, as well as over T-0 and T-D spaces. We also investigate the relational mu-calculus, providing general completeness results for all natural fragments of the mu-calculus over many different classes of relational frames. Unlike most other such proofs for mu-calculi, ours is model theoretic, making an innovative use of a known method from modal logic (the 'final' submodel of the canonical model), which has the twin advantages of great generality and essential simplicity.
引用
收藏
页数：38
相关论文
共 45 条
  • [1] DOMAIN THEORY IN LOGICAL FORM
    ABRAMSKY, S
    [J]. ANNALS OF PURE AND APPLIED LOGIC, 1991, 51 (1-2) : 1 - 77
  • [2] Afshari B, 2017, IEEE S LOG
  • [3] [Anonymous], 2011, IJCAI 2011, DOI DOI 10.5591/978-1-57735-516-8/IJCAI11-149
  • [4] Baltag A., 2022, P 19 INT C PRINC KNO
  • [5] The Topological Mu-Calculus: completeness and decidability
    Baltag, Alexandru
    Bezhanishvili, Nick
    Fernandez-Duque, David
    [J]. 2021 36TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2021,
  • [6] On the Solvability of Inductive Problems: A Study in Epistemic Topology
    Baltag, Alexandru
    Gierasimczuk, Nina
    Smets, Sonja
    [J]. ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2016, (215): : 81 - 98
  • [7] Justified Belief and the Topology of Evidence
    Baltag, Alexandru
    Bezhanishvili, Nick
    Ozgun, Aybuke
    Smets, Sonja
    [J]. LOGIC, LANGUAGE, INFORMATION, AND COMPUTATION, 2016, 9803 : 83 - 103
  • [8] Beklemishev L., 2014, Leo Esakia on duality in modal and intuitionistic logics, V4, P257
  • [9] S4.3 and hereditarily extremally disconnected spaces
    Bezhanishvili, Guram
    Bezhanishvili, Nick
    Lucero-Bryan, Joel
    van Mill, Jan
    [J]. GEORGIAN MATHEMATICAL JOURNAL, 2015, 22 (04) : 469 - 475
  • [10] Bezhanishvili G, 2011, LECT NOTES ARTIF INT, V6618, P16, DOI 10.1007/978-3-642-22303-7_2
12345