论文标题
高维Minkowski Spacetime的期限时间
EXPTIME-hardness of higher-dimensional Minkowski spacetime
论文作者
论文摘要
我们证明了Minkowski Spacetime上基本的时间逻辑的有效性问题的指示时间 - 具有多个空间维度。我们证明了Lightspeed-or-Slower和较慢的访问性关系（以及这些关系的反射性和反思性版本）的结果。作为辅助结果，我们证明了在任何嵌入无限的完整二进制树的框架上的有效性的指数 - 固定性，以满足某些条件。证明是通过减少了两人走廊的窃听游戏。
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.
