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

SCIAVICCO, Guido
Ultimo
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.
2009
978-0-7695-3727-6
Logic, Ontologies, Computer science, Artificial intelligence, Spatial databases, Natural language processing, Constraint theory, Hardware, Real time systems, Africa
File in questo prodotto:
File Dimensione Formato  
time09cr.pdf

solo gestori archivio

Descrizione: Articolo
Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 227.65 kB
Formato Adobe PDF
227.65 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Undecidability_of_Interval_Temporal_Logics_with_the_Overlap_Modality.pdf

solo gestori archivio

Tipologia: Full text (versione editoriale)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 324.88 kB
Formato Adobe PDF
324.88 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/2326769
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact