The finite model property for logics with the tangle modality. (English) Zbl 1437.03087
Summary: The tangle modality is a propositional connective that extends basic modal logic to a language that is expressively equivalent over certain classes of finite frames to the bisimulation-invariant fragments of both first-order and monadic second-order logic. This paper axiomatises several logics with tangle, including some that have the universal modality, and shows that they have the finite model property for Kripke frame semantics. The logics are specified by a variety of conditions on their validating frames, including local and global connectedness properties. Some of the results have been used to obtain completeness theorems for interpretations of tangled modal logics in topological spaces.
MSC:
| 03B45 | Modal logic (including the logic of norms) |
Keywords:
tangle modality; finite model property; Kripke frame; filtration; connected; universal modalityReferences:
| [1] | Blackburn, P., M. de Rijke, and Y. Venema, Modal Logic. Cambridge University Press, 2001. · Zbl 0988.03006 |
| [2] | Dawar, A., and M. Otto, Modal characterisation theorems over special classes of frames. Annals of Pure and Applied Logic 161:1-42, 2009. · Zbl 1185.03027 |
| [3] | Fernández-Duque, D., A sound and complete axiomatization for dynamic topological logic. The Journal of Symbolic Logic 77:947-969, 2012. · Zbl 1256.03025 |
| [4] | Fernández-Duque, D., On the modal definability of simulability by finite transitive models. Studia Logica 98(3):347-373, 2011. · Zbl 1246.03042 · doi:10.1007/s11225-011-9339-x |
| [5] | Fernández-Duque, D., Tangled modal logic for spatial reasoning, in T. Walsh, (ed.), Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI), pp. 857-862. AAAI Press/IJCAI, 2011. |
| [6] | Fernández-Duque, D., Tangled modal logic for topological dynamics. Annals of Pure and Applied Logic 163:467-481, 2012. · Zbl 1248.03033 · doi:10.1016/j.apal.2011.12.018 |
| [7] | Goldblatt, R., Logics of Time and Computation. CSLI Lecture Notes No. 7. CSLI Publications, Stanford University, second edition, 1992. · Zbl 0635.03024 |
| [8] | Goldblatt, R., and I. Hodkinson, Spatial logic of tangled closure operators and modal mu-calculus. Annals of Pure and Applied Logic 168:1032-1090, 2017. doi:10.1016/j.apal.2016.11.006. · Zbl 1422.03034 |
| [9] | Goldblatt, R., and I. Hodkinson, The tangled derivative logic of the real line and zero-dimensional spaces, in L. Beklemishev, S. Demri, and A. Máté, (eds.), Advances in Modal Logic, Volume 11, pp. 342-361. College Publications, 2016. http://www.aiml.net/volumes/volume11/. · Zbl 1400.03042 |
| [10] | Janin D., and I. Walukiewicz, On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic, in U. Montanari and V. Sassone, (eds.), CONCUR ’96: Concurrency Theory, volume 1119 of Lecture Notes in Computer Science, Springer, 1996, pp. 263-277. · Zbl 1514.68171 |
| [11] | Kudinov, A., and V. Shehtman, Derivational modal logics with the difference modality, in G. Bezhanishvili, (ed.), Leo Esakia on Duality in Modal and Intuitionistic Logics, volume 4 of Outstanding Contributions to Logic, Springer, 2014, pp. 291-334. · Zbl 1352.03031 |
| [12] | Lucero-Bryan, J. G., The d-logic of the real line. Journal of Logic and Computation 23(1):121-156, 2013. doi:10.1093/logcom/exr054. · Zbl 1280.03023 · doi:10.1093/logcom/exr054 |
| [13] | Rosen, E., Modal logic over finite structures. Journal of Logic and Computation 6:427-439, 1997. · Zbl 0882.03014 |
| [14] | Segerberg, K., Decidability of S4.1. Theoria 34:7-20, 1968. · doi:10.1111/j.1755-2567.1968.tb00335.x |
| [15] | Shehtman, V., Derived sets in Euclidean spaces and modal logic. Technical Report X-1990-05, University of Amsterdam, 1990. http://www.illc.uva.nl/Research/Publications/Reports/X-1990-05.text.pdf. · Zbl 1246.03042 |
| [16] | Shehtman, V., «Everywhere» and «Here». Journal of Applied Non-Classical Logics 9(2-3):369-379, 1999. · Zbl 0993.03020 |
| [17] | Shehtman, V., Modal logic of Topological Spaces. Habilitation thesis, Moscow, 2000. In Russian. |
| [18] | Tarski, A., A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics 5:285-309, 1955. · Zbl 0064.26004 · doi:10.2140/pjm.1955.5.285 |
| [19] | van Benthem, J. F. A. K., Modal Correspondence Theory. PhD thesis, University of Amsterdam, 1976. · Zbl 0799.03010 |
| [20] | van Benthem, J. F. A. K., Modal Logic and Classical Logic. Bibliopolis, Naples, 1983. |
| [21] | Zakharyaschev, M., A sufficient condition for the finite model property of modal logics above K4. Bulletin of the IGPL 1:13-21, 1993. · Zbl 0799.03010 · doi:10.1093/jigpal/1.1.13 |
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.
