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: http://dx.doi.org/10.1093/logcom/9.6.897
*Subscription may be required
Free to read: https://www.researchgate.net/publication/220388384...
*No subscription required

Abstract

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.

Publication Type: Journal Article
Murdoch Affiliation: School of Information Technology
Publisher: Oxford University Press
URI: http://researchrepository.murdoch.edu.au/id/eprint/36093
Item Control Page Item Control Page