In our contribution, we study the effects of adding past operators to interval temporal logics. We focus our attention on the representative case of Propositional Neighborhood Logic (⎯⎯⎯⎯ for short), taking into consideration different temporal domains. ⎯⎯⎯⎯ is the proper fragment of Halpern and Shoham’s modal logic of intervals with modalities for Allen’s relations meets (future modality) and met by (past modality). We first prove that, unlike what happens with point-based linear temporal logic, ⎯⎯⎯⎯ is strictly more expressive than its future fragment A. Then, we show that there is a log-space reduction from the satisfiability problem for ⎯⎯⎯⎯ over ℤ to its satisfiability problem over ℕ. Compared to the corresponding reduction for point-based linear temporal logic, the one for ⎯⎯⎯⎯ turns out to be much more involved. Finally, we prove that ⎯⎯⎯⎯ is able to separate ℚ and ℝ, while A is not.

The Importance of the Past in Interval Temporal Logics: The Case of Propositional Neighborhood Logic

SALA, Pietro
2012-01-01

Abstract

In our contribution, we study the effects of adding past operators to interval temporal logics. We focus our attention on the representative case of Propositional Neighborhood Logic (⎯⎯⎯⎯ for short), taking into consideration different temporal domains. ⎯⎯⎯⎯ is the proper fragment of Halpern and Shoham’s modal logic of intervals with modalities for Allen’s relations meets (future modality) and met by (past modality). We first prove that, unlike what happens with point-based linear temporal logic, ⎯⎯⎯⎯ is strictly more expressive than its future fragment A. Then, we show that there is a log-space reduction from the satisfiability problem for ⎯⎯⎯⎯ over ℤ to its satisfiability problem over ℕ. Compared to the corresponding reduction for point-based linear temporal logic, the one for ⎯⎯⎯⎯ turns out to be much more involved. Finally, we prove that ⎯⎯⎯⎯ is able to separate ℚ and ℝ, while A is not.
2012
978-3-642-29413-6
Interval Temporal Logic, First Order Logic, Decidability
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: https://hdl.handle.net/11562/932433
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact