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.
Undecidability of interval temporal logics with the overlap modality / Davide Bresolin; Dario Della Monica; Valentin Goranko; Angelo Montanari; Guido Sciavicco. - STAMPA. - (2009), pp. 88-95. (Intervento presentato al convegno TIME 2009: 16th International Symposium on Temporal Representation and Reasoning tenutosi a Bressanone-Brixen nel Luglio) [10.1109/TIME.2009.24].
Undecidability of interval temporal logics with the overlap modality
BRESOLIN, DAVIDE;
2009
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
