Interval temporal logics provide a natural framework for temporal reasoning about interval structures over linearly ordered domains, where intervals are taken as first-class citizens. Their expressive power and computational behavior mainly depend on two parameters: the set of modalities they feature and the linear orders over which they are interpreted. In this paper, we consider all fragments of Halpern and Shoham's interval temporal logic HS with a decidable satisfiability problem over the rationals, and we provide a complete classification of them in terms of their expressiveness and computational complexity by solving the last few open problems.
Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals
Sala, P.;
2019-01-01
Abstract
Interval temporal logics provide a natural framework for temporal reasoning about interval structures over linearly ordered domains, where intervals are taken as first-class citizens. Their expressive power and computational behavior mainly depend on two parameters: the set of modalities they feature and the linear orders over which they are interpreted. In this paper, we consider all fragments of Halpern and Shoham's interval temporal logic HS with a decidable satisfiability problem over the rationals, and we provide a complete classification of them in terms of their expressiveness and computational complexity by solving the last few open problems.
| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0890540119300173-main.pdf
non disponibili
Tipologia:
Versione dell'editore
Licenza:
Accesso ristretto
Dimensione
1.03 MB
Formato
Adobe PDF
|
1.03 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
