The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Their computational behaviour is generally bad, and several restrictions have been considered in order to define decidable and computationally affordable temporal logics based on intervals. In this paper we take inspiration from Golumbic and Shamir's coarser interval algebras, which generalize the classical Allen's Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham's logic (HS). We prove that one of them (denoted here by HS7) is still generally undecidable, while the other one (HS3) becomes, perhaps surprisingly, PSpace-complete, at least in the finite case.

On Coarser Interval Temporal Logics and their Satisfiability Problem

SCIAVICCO, Guido
2015

Abstract

The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Their computational behaviour is generally bad, and several restrictions have been considered in order to define decidable and computationally affordable temporal logics based on intervals. In this paper we take inspiration from Golumbic and Shamir's coarser interval algebras, which generalize the classical Allen's Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham's logic (HS). We prove that one of them (denoted here by HS7) is still generally undecidable, while the other one (HS3) becomes, perhaps surprisingly, PSpace-complete, at least in the finite case.
978-3-319-24597-3
Interval, Temporal Logic
File in questo prodotto:
File Dimensione Formato  
caepia15-MPSS.pdf

accesso aperto

Descrizione: Articolo
Tipologia: Pre-print
Licenza: PUBBLICO - Pubblico con Copyright
Dimensione 377.46 kB
Formato Adobe PDF
377.46 kB Adobe PDF Visualizza/Apri

I documenti in IRIS 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: http://hdl.handle.net/11392/2330268
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact