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
DELLA MONICA, Dario;MONTANARI, Angelo;
2009-01-01
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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
time09cr.pdf
non disponibili
Tipologia:
Documento in Pre-print
Licenza:
Non pubblico
Dimensione
227.65 kB
Formato
Adobe PDF
|
227.65 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
