The undecidability of iterated modal relativization

Studia Logica 79 (3):373 - 407 (2005)
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.
Keywords Philosophy   Logic   Mathematical Logic and Foundations   Computational Linguistics
Categories (categorize this paper)
DOI 10.2307/20016697
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 16,667
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
Jelle Gerbrandy & Willem Groeneveld (1997). Reasoning About Information Change. Journal of Logic, Language and Information 6 (2):147-169.

Add more references

Citations of this work BETA
Johan van Benthem (2007). Dynamic Logic for Belief Revision. Journal of Applied Non-Classical Logics 17 (2):129-155.
Hans P. van Ditmarsch (2005). The Case of the Hidden Hand. Journal of Applied Non-Classical Logics 15 (4):437-452.

View all 8 citations / Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

5 ( #377,318 of 1,726,249 )

Recent downloads (6 months)

2 ( #289,836 of 1,726,249 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.