Undecidability of Interval Temporal Logics with the Overlap Modality
Davide Bresolin, Dario Della Monica, Val Goranko, Angelo Montanari, Guido Sciavicco · 2009
We investigate fragments of Halpern-Shoham's interval logic HS involving the modal operators for the relations of left or right overlap of intervals. We prove that most of these fragments are undecidable, by employing a non-trivial reduction from the octant tiling problem.