Horn fragments of Halpern-Shoham logic: complexity vs expressiveness

VCLA hosted a talk by Przemysław Andrzej Wałęga

ABSTRACT

Halpern-Shoham logic (HS) is a highly expressive but undecidable interval temporal logic. The main line of research in the area consists in searching for decidable and low complexity fragments of this logic. The full HS is referential, i.e., it enables us to label intervals and then to refer to a chosen interval with a concrete label. Although referentiality is crucial in temporal knowledge representation, it is an open problem which HS fragments enjoy this property. During the talk I will present my recent results on expressive power and computational complexity of Horn HS fragments. I will show which HS fragments are referential and which are not. In order to regain referentiality I will hybridize particular fragments and study their computational complexity. The obtained results give us better understanding of Horn HS fragments and shed light on the interplay between their expressive power and computational complexity.