UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

The temporal logic of two dimensional Minkowski spacetime is decidable

Hirsch, R; Reynolds, M; (2018) The temporal logic of two dimensional Minkowski spacetime is decidable. Journal of Symbolic Logic , 83 (3) pp. 829-867. 10.1017/jsl.2017.79. Green open access

[img]
Preview
Text
decidability_minkowski_revised.pdf - Accepted version

Download (493kB) | Preview

Abstract

We consider Minkowski spacetime, the set of all point-events of spacetime under the relation of causal accessibility. That is, x can access y if an electromagnetic or (slower than light) mechanical signal could be sent from x to y. We use Prior’s tense language of F and P representing causal accessibility and its converse relation. We consider two versions, one where the accessibility relation is reflexive and one where it is irreflexive. In either case it has been an open problem, for decades, whether the logic is decidable or axiomatisable. We make a small step forward by proving, in each case, that the set of valid formulas over two-dimensional Minkowski spacetime is decidable and that the complexity of each problem is PSPACE-complete. A consequence is that the temporal logic of intervals with real endpoints under either the containment relation or the strict containment relation is PSPACE-complete, the same is true if the interval accessibility relation is “each endpoint is not earlier”, or its irreflexive restriction. We provide a temporal formula that distinguishes between three-dimensional and two-dimensional Minkowski spacetime and another temporal formula that distinguishes the two-dimensional case where the underlying field is the real numbers from the case where instead we use the rational numbers.

Type: Article
Title: The temporal logic of two dimensional Minkowski spacetime is decidable
Open access status: An open access version is available from UCL Discovery
DOI: 10.1017/jsl.2017.79
Publisher version: https://doi.org/10.1017/jsl.2017.79
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10037692
Downloads since deposit
46Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item