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).
Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/11562/473691
Titolo: | Interval Temporal Logics over Finite Linear Orders: the Complete Picture |
Autori: | |
Data di pubblicazione: | 2012 |
Serie: | |
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). |
Handle: | http://hdl.handle.net/11562/473691 |
ISBN: | 9781614990987 |
Appare nelle tipologie: | 04.01 Contributo in atti di convegno |
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.