Hirsch, R;
McLean, B;
(2022)
EXPTIME-hardness of higher-dimensional Minkowski spacetime.
In: Fernández-Duque, D and Palmigiano, A and Pinchinat, S, (eds.)
Advances in Modal Logic.
(pp. pp. 491-505).
College Publications: London, UK.
Preview |
Text
2206.06866(3).pdf - Other Download (236kB) | Preview |
Abstract
We prove the EXPTIME-hardness of the validity problem for the basic temporal logic on Minkowski spacetime with more than one space dimension. We prove this result for both the lightspeed-or-slower and the slower-than-light accessibility relations (and for both the irreflexive and the reflexive versions of these relations). As an auxiliary result, we prove the EXPTIME-hardness of validity on any frame for which there exists an embedding of the infinite complete binary tree satisfying certain conditions. The proof is by a reduction from the two-player corridor-tiling game.
| Type: | Proceedings paper |
|---|---|
| Title: | EXPTIME-hardness of higher-dimensional Minkowski spacetime |
| ISBN-13: | 9781848904132 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | http://www.aiml.net/volumes/volume14/ |
| 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 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/10188143 |
Archive Staff Only
 |
View Item |
