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. In this paper, we identify all fragments of Halpern and Shoham's interval temporal logic HS whose finite satisfiability problem is decidable. We classify them in terms of both relative expressive power and complexity. We show that there are exactly 62 expressively-different decidable fragments, whose complexity ranges from NP-complete to non-primitive recursive (all other HS fragments have been already shown to be undecidable).

Interval Temporal Logics over Finite Linear Orders: the Complete Picture

BRESOLIN, Davide;SALA, Pietro;
2012

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. In this paper, we identify all fragments of Halpern and Shoham's interval temporal logic HS whose finite satisfiability problem is decidable. We classify them in terms of both relative expressive power and complexity. We show that there are exactly 62 expressively-different decidable fragments, whose complexity ranges from NP-complete to non-primitive recursive (all other HS fragments have been already shown to be undecidable).
9781614990987
Interval logic; decidability; expressivity
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11562/473691
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 9
social impact