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

06/26/2018
by   Robin Hirsch, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset