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.
On the complexity of fragments of the modal logic of Allen’s relations over dense structures / Bresolin, Davide; Monica, Dario Della; Montanari, Angelo; Sala, Pietro; Sciavicco, Guido. - STAMPA. - 8977:(2015), pp. 511-523. (Intervento presentato al convegno 9th International Conference on Language and Automata Theory and Applications, LATA 2015 tenutosi a fra nel 2015) [10.1007/978-3-319-15579-1_40].
On the complexity of fragments of the modal logic of Allen’s relations over dense structures
BRESOLIN, DAVIDE;
2015
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 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
