Interval temporal logics provide a natural framework for temporal reasoning about interval structures over linearly ordered domains, where intervals are taken as the primitive ontological entities. The most influential propositional interval-based logic is probably Halpern and Shoham’s Modal Logic of Time Intervals, a.k.a. HS. While most studies focused on the computational properties of the syntactic fragments that arise by considering only a subset of the set of modalities, the fragments that are obtained by weakening the propositional side have received very scarce attention. Here, we approach this problem by considering various sub-propositional fragments of HS, such as the so-called Horn, Krom, and core fragment. We prove that the Horn fragment of HS is undecidable on every interesting class of linearly ordered sets, and we briefly discuss the difficulties that arise when considering the other fragments. © Springer International Publishing Switzerland 2014.

Sub-Propositional Fragments of the Interval Temporal Logic of Allen's Relations

SCIAVICCO, Guido
Ultimo
2014

Abstract

Interval temporal logics provide a natural framework for temporal reasoning about interval structures over linearly ordered domains, where intervals are taken as the primitive ontological entities. The most influential propositional interval-based logic is probably Halpern and Shoham’s Modal Logic of Time Intervals, a.k.a. HS. While most studies focused on the computational properties of the syntactic fragments that arise by considering only a subset of the set of modalities, the fragments that are obtained by weakening the propositional side have received very scarce attention. Here, we approach this problem by considering various sub-propositional fragments of HS, such as the so-called Horn, Krom, and core fragment. We prove that the Horn fragment of HS is undecidable on every interesting class of linearly ordered sets, and we briefly discuss the difficulties that arise when considering the other fragments. © Springer International Publishing Switzerland 2014.
2014
978-3-319-11557-3
File in questo prodotto:
File Dimensione Formato  
jelia2014-62.pdf

solo gestori archivio

Descrizione: versione pre print
Tipologia: Pre-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 420.18 kB
Formato Adobe PDF
420.18 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
LNAI 8761 - Logics in Artificial Intelligence_2014_Sciavicco.pdf

solo gestori archivio

Descrizione: versione editoriale
Tipologia: Full text (versione editoriale)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 629.62 kB
Formato Adobe PDF
629.62 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/2328920
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 12
social impact