On the complexity of fragments of the modal logic of Allen’s relations over dense structures. (English) Zbl 1451.03020
Dediu, Adrian-Horia (ed.) et al., Language and automata theory and applications. 9th international conference, LATA 2015, Nice, France, March 2–6, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8977, 511-523 (2015).
Summary: 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 behaviour and expressive power 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 class of all dense linear orders, and we provide a complete classification of them in terms of their complexity and expressiveness by solving the last two open cases.
For the entire collection see [Zbl 1331.68009].
For the entire collection see [Zbl 1331.68009].
MSC:
| 03B44 | Temporal logic |
| 03D15 | Complexity of computation (including implicit computational complexity) |
