zbMATH — the first resource for mathematics

The importance of the past in interval temporal logics: the case of propositional neighborhood logic. (English) Zbl 1356.03061
Artikis, Alexander (ed.) et al., Logic programs, norms and action. Essays in honor of Marek J. Sergot on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-642-29413-6/pbk). Lecture Notes in Computer Science 7360. Lecture Notes in Artificial Intelligence, 79-102 (2012).
Summary: 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 (\( A \overline A\) for short), taking into consideration different temporal domains. \(A \overline A\) is the proper fragment of J. Y. Halpern and Y. Shoham’s [J. Assoc. Comput. Mach. 38, No. 4, 935–962 (1991; Zbl 0799.68175)] modal logic of intervals with modalities for J. F. Allen’s [Commun. ACM 26, 832–843 (1983; Zbl 0519.68079)] relations meets (future modality) and met by (past modality). We first prove that, unlike what happens with point-based linear temporal logic, \(A \overline A\) is strictly more expressive than its future fragment A. Then, we show that there is a log-space reduction from the satisfiability problem for \(A \overline A\) over \(\mathbb Z\) to its satisfiability problem over \(\mathbb N\). Compared to the corresponding reduction for point-based linear temporal logic, the one for \(A \overline A\) turns out to be much more involved. Finally, we prove that \(A \overline A\) is able to separate \(\mathbb Q\) and \(\mathbb R\), while A is not.
For the entire collection see [Zbl 1241.68007].

03B44 Temporal logic
Full Text: DOI