Skip to main content
SpringerLink
Log in

The Undecidability of Iterated Modal Relativization

  • Published:
Studia Logica Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. BALTAG, ALEXANDRU, and LAWRENCE S. MOSS, ‘Logics for epistemic programs’, Synthese 139, no. 2, (2004), 165–224.

    Article  Google Scholar 

  2. 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.

  3. BALTAG, ALEXANDRU, LAWRENCE S. MOSS, and SŁLAWOMIR SOLECKI, Revised version of [2], to appear.

  4. BERGER, ROBERT, The Undecidability of the Domino Problem, Memoirs of the American Mathematical Society No. 66, 1966.

  5. BLACKBURN, PATRICK, MAARTEN DE RIJKE, and YDE VENEMA, Modal Logic, Cambridge Tracts in Theoretical Computer Science, vol. 53, Cambridge University Press, 2001.

  6. BÖRGER, EGON, ERICH GRÄDEL, and YURI GUREVICH, The Classical Decision Problem, Springer-Verlag, Berlin, 1997.

    Google Scholar 

  7. DAWAR, ANUJ, ERICH GRÄDEL, and STEPHAN KREUTZER, ‘Infiationary fixed points in modal logic’, ACM Transactions on Computational Logic, to appear.

  8. DERSHOWITZ, NACHUM, ‘Orderings for term-rewriting systems’, Theoretical Computer Science 17 (1982), 279–301.

    Article  Google Scholar 

  9. 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.

    Google Scholar 

  10. GERBRANDY, JELLE, ‘Dynamic epistemic logic’, in Lawrence S. Moss, et al., (eds.), Logic, Language, and Information, vol. 2, CSLI Publications, Stanford University, 1999.

  11. GERBRANDY, JELLE, Bisimulations on Planet Kripke, Ph.D. dissertation, University of Amsterdam, 1999.

  12. GERBRANDY, JELLE, and WILLEM GROENEVELD, ‘Reasoning about information change’, Journal of Logic, Language, and Information 6 (1997), 147–169.

    Google Scholar 

  13. 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.

  14. 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.

  15. HAREL, DAVID, DEXTER C. KOZEN, and J. TIURYN, Dynamic Logic, MIT Press, Cambridge Mass., 2000.

    Google Scholar 

  16. 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.

    Google Scholar 

  17. MOSCHOVAKIS, YIANNIS N., ‘On nonmonotone inductive definability’, Fundamenta Mathematicae 82 (1974–75), 39–83.

    Google Scholar 

  18. 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.

  19. PLAZA, JAN, ‘Logics of public communications’, Proceedings, 4th International Symposium on Methodologies for Intelligent Systems, 1989.

  20. VAN BENTHEM, JOHAN, ‘ ‘One is a lonely number’: on the logic of communication’, ILLC Research Report PP–2003–07, Amsterdam, 2003.

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Indiana University, Bloomington, IN, 47405-7106, USA

    Joseph S. Miller & Lawrence S. Moss

Authors
  1. Joseph S. Miller
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lawrence S. Moss
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joseph S. Miller.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11225-005-3612-9

Keywords

Search

Navigation