Catalog Home Page

Undecidability of compass logic

Marx, M. and Reynolds, M. (1999) Undecidability of compass logic. Journal of Logic and Computation, 9 (6). pp. 897-914.

Link to Published Version:
*Subscription may be required
Free to read:
*No subscription required


It is known that the tiling technique can be used to give simple proofs of undecidability of various two-dimensional modal and temporal logics. However, up until now, the simplest two-dimensional temporal logic, the compass logic of Venema, has eluded such treatment. We present a new coding of an enumeration of the tiling plane which enables us to show that the compass logic is undecidable.

Item Type: Journal Article
Murdoch Affiliation: School of Information Technology
Publisher: Oxford University Press
Item Control Page Item Control Page