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

On Coarser Interval Temporal Logics and their Satisfiability Problem

SALA, Pietro;
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
Interval Temporal Logic, Coarse Intervals, Satisfiability Problem, Interval Algebra (IA), Finite Case
File in questo prodotto:
File Dimensione Formato  
Muñoz-Velasco2015_Chapter_OnCoarserIntervalTemporalLogic (1).pdf

non disponibili

Tipologia: Versione dell'editore
Licenza: Accesso ristretto
Dimensione 422.76 kB
Formato Adobe PDF
422.76 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.

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