Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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(s): School of Information Technology
Publisher: Oxford University Press
Item Control Page Item Control Page