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

The temporal logic of two-dimensional Minkowski spacetime with slower-than-light accessibility is decidable

Hirsch, R; McLean, B; (2018) The temporal logic of two-dimensional Minkowski spacetime with slower-than-light accessibility is decidable. In: Bezhanishvili, G and D'Agostino, G and Metcalfe, G and Studer, T, (eds.) Advances in Modal Logic, Volume 12. (pp. pp. 347-366). AiML: Bern, Switzerland. Green open access

[thumbnail of Hirsch_Hirsch-McLean.pdf]
Preview
Text
Hirsch_Hirsch-McLean.pdf - Published Version

Download (474kB) | Preview

Abstract

We work primarily with the Kripke frame consisting of two-dimensional Minkowski spacetime with the irreflexive accessibility relation ‘can reach with a slower-than-light signal’. We show that in the basic temporal language, the set of validities over this frame is decidable. We then refine this to PSPACE-complete. In both cases the same result for the corresponding reflexive frame follows immediately. With a little more work we obtain PSPACE-completeness for the validities of the Halpern–Shoham logic of intervals on the real line with two different combinations of modalities.

Type: Proceedings paper
Title: The temporal logic of two-dimensional Minkowski spacetime with slower-than-light accessibility is decidable
Event: Twelfth conference on "Advances in Modal logic,"
ISBN: 1904987206
Open access status: An open access version is available from UCL Discovery
Publisher version: http://www.aiml.net/volumes/volume12/
Language: English
Additional information: This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: temporal logic, basic temporal language, Minkowski spacetime, frame validity, Halpern–Shoham logic.
UCL classification: UCL
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/10090241
Downloads since deposit
15Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item