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. Their computational behavior mainly depends on two parameters: the set of modalities they feature and the linear orders over which they are interpreted. In this paper, we identify all fragments of Halpern and Shoham's interval temporal logic HS with a decidable satisfiability problem over the class of strongly discrete linear orders as well as over its relevant subclasses (the class of finite linear orders, Z, N, and Z-). We classify them in terms of both their relative expressive power and their complexity, which ranges from NP-completeness to non-primitive recursiveness.
Interval Temporal Logics over Strongly Discrete Linear Orders: Expressiveness and Complexity
Della Monica D;MONTANARI, Angelo;
2014-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 the primitive ontological entities. Their computational behavior mainly depends on two parameters: the set of modalities they feature and the linear orders over which they are interpreted. In this paper, we identify all fragments of Halpern and Shoham's interval temporal logic HS with a decidable satisfiability problem over the class of strongly discrete linear orders as well as over its relevant subclasses (the class of finite linear orders, Z, N, and Z-). We classify them in terms of both their relative expressive power and their complexity, which ranges from NP-completeness to non-primitive recursiveness.File | Dimensione | Formato | |
---|---|---|---|
TCS2014cr.pdf
non disponibili
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non pubblico
Dimensione
996.16 kB
Formato
Adobe PDF
|
996.16 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.