Abstract
In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 Σ11–complete. Two of these fragments do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 Σ01–complete. These results go via reduction to problems concerning domino systems.
Similar content being viewed by others
References
BALTAG, ALEXANDRU, and LAWRENCE S. MOSS, ‘Logics for epistemic programs’, Synthese 139, no. 2, (2004), 165–224.
BALTAG, ALEXANDRU, LAWRENCE S. MOSS, and SŁLAWOMIR SOLECKI, ‘The logic of common knowledge, public announcements, and private suspicions’, Proceedings of TARK–VII (Theoretical Aspects of Rationality and Knowledge), 1998.
BALTAG, ALEXANDRU, LAWRENCE S. MOSS, and SŁLAWOMIR SOLECKI, Revised version of [2], to appear.
BERGER, ROBERT, The Undecidability of the Domino Problem, Memoirs of the American Mathematical Society No. 66, 1966.
BLACKBURN, PATRICK, MAARTEN DE RIJKE, and YDE VENEMA, Modal Logic, Cambridge Tracts in Theoretical Computer Science, vol. 53, Cambridge University Press, 2001.
BÖRGER, EGON, ERICH GRÄDEL, and YURI GUREVICH, The Classical Decision Problem, Springer-Verlag, Berlin, 1997.
DAWAR, ANUJ, ERICH GRÄDEL, and STEPHAN KREUTZER, ‘Infiationary fixed points in modal logic’, ACM Transactions on Computational Logic, to appear.
DERSHOWITZ, NACHUM, ‘Orderings for term-rewriting systems’, Theoretical Computer Science 17 (1982), 279–301.
FLUM, JORG, ‘On the (infinite) model theory of fixed-point logics’, in Models, Algebras, and Proofs (Bogot, 199), Lecture Notes in Pure and Applied Mathematics, vol. 203, Marcel Dekker, New York, 1999, pp. 67–75.
GERBRANDY, JELLE, ‘Dynamic epistemic logic’, in Lawrence S. Moss, et al., (eds.), Logic, Language, and Information, vol. 2, CSLI Publications, Stanford University, 1999.
GERBRANDY, JELLE, Bisimulations on Planet Kripke, Ph.D. dissertation, University of Amsterdam, 1999.
GERBRANDY, JELLE, and WILLEM GROENEVELD, ‘Reasoning about information change’, Journal of Logic, Language, and Information 6 (1997), 147–169.
GRÄDEL, ERICH, and STEPHAN KREUTZER, ‘Will defiation lead to depletion?’, On non-monotone fixed-point inductions, IEEE Conference on Logic in Computer Science (LICS’03), pp. 158–167.
HAREL, DAVID, ‘Recurring dominoes: making the highly undecidable highly understandable’, Topics in the Theory of Computation (Borgholm, 1983), North-Holland Math. Stud., 102, North-Holland, Amsterdam, 1985, pp. 51–71.
HAREL, DAVID, DEXTER C. KOZEN, and J. TIURYN, Dynamic Logic, MIT Press, Cambridge Mass., 2000.
LIN, YU CAI, ‘The decision problems about the periodic solutions of the domino problems’, Chinese Annals of Mathematics, Series B 5, no. 4, (1984), 721–726.
MOSCHOVAKIS, YIANNIS N., ‘On nonmonotone inductive definability’, Fundamenta Mathematicae 82 (1974–75), 39–83.
PLAISTED, DAVID A., ‘Termination orderings’, in D. Gabbay, et al. (eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, vol. I, pp. 273–364.
PLAZA, JAN, ‘Logics of public communications’, Proceedings, 4th International Symposium on Methodologies for Intelligent Systems, 1989.
VAN BENTHEM, JOHAN, ‘ ‘One is a lonely number’: on the logic of communication’, ILLC Research Report PP–2003–07, Amsterdam, 2003.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Miller, J.S., Moss, L.S. The Undecidability of Iterated Modal Relativization. Stud Logica 79, 373–407 (2005). https://doi.org/10.1007/s11225-005-3612-9
Received:
Issue Date:
DOI: https://doi.org/10.1007/s11225-005-3612-9