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.

Davide Bresolin, Dario Della Monica, Angelo Montanari, Pietro Sala, Guido Sciavicco (2014). Interval temporal logics over strongly discrete linear orders: Expressiveness and complexity. THEORETICAL COMPUTER SCIENCE, 560(3), 269-291 [10.1016/j.tcs.2014.03.033].

Interval temporal logics over strongly discrete linear orders: Expressiveness and complexity

BRESOLIN, DAVIDE;
2014

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.
2014
Davide Bresolin, Dario Della Monica, Angelo Montanari, Pietro Sala, Guido Sciavicco (2014). Interval temporal logics over strongly discrete linear orders: Expressiveness and complexity. THEORETICAL COMPUTER SCIENCE, 560(3), 269-291 [10.1016/j.tcs.2014.03.033].
Davide Bresolin;Dario Della Monica;Angelo Montanari;Pietro Sala;Guido Sciavicco
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/403158
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 37
  • ???jsp.display-item.citation.isi??? 21
social impact