|
|
Technical Report TR586:
The Undecidability of Iterated Modal Relativization
Joseph S. Miller and Lawrence S. Moss
Unknown Date, 26 pages
- 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 three fragments of logic of iterated relativization and transitive closure are $\Sigma^1_1$-complete. Of these, two 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 $\Sigma^0_1$-complete. These results go via reduction to problems concerning domino systems.
- Available as:
-
There is help available
if you want further information about the available file formats and
software to display and print these files. Return to the Technical Report Index
|
