EXPTIME-hardness of higher-dimensional Minkowski spacetime

Temporal logic (03B44) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Special relativity (83A05)

arXiv classification

cs.LO math.LO

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.

This page was built for publication: EXPTIME-hardness of higher-dimensional Minkowski spacetime

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402054)