×

Partitioning Kripke frames of finite height. (English. Russian original) Zbl 1371.03025

Izv. Math. 81, No. 3, 592-617 (2017); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 81, No. 3, 134-159 (2017).
This paper touches on a very old and interesting problem in modal logic and its decidability. Particularly, when would the systems where the modal relation \(R\) satisfies \(R^n \subseteq R^m\) be decidable?
This problem is deeper than it looks and only the simplest cases are known. The current paper approaches this open problem focusing on frames and their height. As such, it introduces some rigid criteria to handle the frames and their partitions. The conditions are not so unnatural but certainly changes the original problem.
The main result of this dense paper associates the restricted frames (called tuned, in this case) to general frames where \(R^n \subseteq R^m\) and shows their decidability.
Reviewer: Can Baskent (Bath)

MSC:

03B45 Modal logic (including the logic of norms)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 2003 The description logic handbook. Theory, implementation, and applications (Cambridge: Cambridge Univ. Press)
[2] Vardi M. Y. 2007 Automata-theoretic techniques for temporal reasoning Handbook of modal logic3 971-989 · doi:10.1016/S1570-2464(07)80020-6
[3] Goranko V. and Otto M. 2007 Model theory of modal logic Handbook of modal logic3 249-329 · doi:10.1016/S1570-2464(07)80008-5
[4] Boolos G. 1993 The logic of provability (Cambridge: Cambridge Univ. Press)
[5] Smullyan R. M. and Fitting M. 1996 Oxford Logic Guides34 (New York: Oxford Univ. Press)
[6] Venema Y. 1995 Cylindric modal logic J. Symbolic Logic60 591-623 · Zbl 0830.03008 · doi:10.2307/2275853
[7] Lewis C. I. and Langford C. H. 1932 Symbolic logic (New York-London: Century)
[8] McKinsey J. C. C. and Tarski A. 1948 Some theorems about the sentential calculi of Lewis and Heyting J. Symbolic Logic13 1-15 · Zbl 0037.29409 · doi:10.2307/2268135
[9] McKinsey J. C. C. 1941 A solution of the decision problem for the Lewis systems S2 and S4, with an application to topology J. Symbolic Logic6 117-134 · JFM 67.0974.01 · doi:10.2307/2267105
[10] Jónsson B. and Tarski A. 1951 Boolean algebras with operators. I Amer. J. Math.73 891-939 · Zbl 0045.31505 · doi:10.2307/2372123
[11] Jankov V. A. 1968 Constructing a sequence of strongly independent superintuitionistic propositional calculi Dokl. Akad. Nauk SSSR181 33-34
[12] Gödel K. 1933 Eine Interpretation des intuitionistischen Aussagenkalküls Ergebnisse eines math. Kolloquiums4 39-40 · JFM 59.0866.01
[13] Solovay R. M. 1976 Provability interpretations of modal logic Israel J. Math.25 287-304 · Zbl 0352.02019 · doi:10.1007/BF02757006
[14] Lemmon E. J. and Scott D. 1966 American Philosophical Quarterly, Monograph Series11 (Oxford: Stanford Univ.)
[15] Segerberg K. 1968 Decidability of four modal logics Theoria34 21-25 · doi:10.1111/j.1755-2567.1968.tb00336.x
[16] Gabbay D. M. 1972 A general filtration method for modal logics J. Philos. Logic1 29-34 · Zbl 0248.02025 · doi:10.1007/BF00649988
[17] Chagrov A. and Zakharyaschev M. 1997 Oxford Logic Guides35 (New York: Oxford Univ. Press)
[18] Wolter F. and Zakharyaschev M. 2007 Modal decision problems Handbook of modal logic3 427-489 · doi:10.1016/S1570-2464(07)80010-3
[19] Shehtman V. B. 2005 Filtration via bisimulation Advances in modal logic 289-308 · Zbl 1102.03021
[20] Segerberg K. 1973 Franzen’s proof of Bull’s theorem Ajatus35 216-221 · Zbl 0299.02021
[21] Segerberg K. 1971 Filosofska Studier13 (Uppsala: Uppsala Univ.)
[22] Maksimova L. L. 1975 Finite-level modal logics Algebra i Logika14 304-319 · doi:10.1007/BF01668553
[23] Jansana R. 1994 Some logics related to von Wright’s logic of place Notre Dame J. Formal Logic35 88-98 · Zbl 0801.03015 · doi:10.1305/ndjfl/1040609296
[24] Kudinov A. and Shapirovsky I. 2011 Finite model property of pretransitive analogs of S5 Topology, algebra and categories in logic (TACL 2011) 261-264
[25] Blackburn P., Rijke M. de and Venema Y. 2001 Cambridge Tracts Theoret. Comput. Sci.53 (Cambridge: Cambridge Univ. Press) · doi:10.1017/CBO9781107050884
[26] Matsumoto K. 1955 Reduction theorem in Lewis’ sentential calculi Math. Japon.3 133-135 · Zbl 0066.00903
[27] Gabbay D. M., Shehtman V. B. and Skvortsov D. P. 2009 Stud. Logic Found. Math.153 (Amsterdam: Elsevier B. V.)
[28] Kikot S., Shapirovsky I. and Zolin E. 2014 Filtration safe operations on frames Advances in modal logic 333-352 · Zbl 1385.03020
[29] Miyazaki Y. 2005 Normal modal logics containing KTB with some finiteness conditions Advances in modal logic 171-190 · Zbl 1102.03019
[30] Kostrzycka Z. 2008 On non-compact logics in NEXT(KTB) MLQ Math. Log. Q.54 617-624 · Zbl 1172.03012 · doi:10.1002/malq.200710056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.