Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Blackburn, P., M. de Rijke, and Y. Venema, Modal Logic. Cambridge University Press, 2001.
Dawar, A., and M. Otto, Modal characterisation theorems over special classes of frames. Annals of Pure and Applied Logic 161:1–42, 2009.
Fernández-Duque, D., A sound and complete axiomatization for dynamic topological logic. The Journal of Symbolic Logic 77:947–969, 2012.
Fernández-Duque, D., On the modal definability of simulability by finite transitive models. Studia Logica 98(3):347–373, 2011.
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.
Fernández-Duque, D., Tangled modal logic for topological dynamics. Annals of Pure and Applied Logic 163:467–481, 2012.
Goldblatt, R., Logics of Time and Computation. CSLI Lecture Notes No. 7. CSLI Publications, Stanford University, second edition, 1992.
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.
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/.
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.
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.
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.
Rosen, E., Modal logic over finite structures. Journal of Logic and Computation 6:427–439, 1997.
Segerberg, K., Decidability of S4.1. Theoria 34:7–20, 1968.
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.
Shehtman, V., «Everywhere» and «Here». Journal of Applied Non-Classical Logics 9(2–3):369–379, 1999.
Shehtman, V., Modal logic of Topological Spaces. Habilitation thesis, Moscow, 2000. In Russian.
Tarski, A., A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics 5:285–309, 1955.
van Benthem, J. F. A. K., Modal Correspondence Theory. PhD thesis, University of Amsterdam, 1976.
van Benthem, J. F. A. K., Modal Logic and Classical Logic. Bibliopolis, Naples, 1983.
Zakharyaschev, M., A sufficient condition for the finite model property of modal logics above K4. Bulletin of the IGPL 1:13–21, 1993.
Acknowledgements
The authors would like to thank the referees for their very helpful comments and suggestions. The second author was supported by UK EPSRC overseas travel grant EP-L020750-1.
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by Yde Venema
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Goldblatt, R., Hodkinson, I. The Finite Model Property for Logics with the Tangle Modality. Stud Logica 106, 131–166 (2018). https://doi.org/10.1007/s11225-017-9732-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-017-9732-1