Przemysław Wałęga

Horn fragments of Halpern-Shoham logic and their hybrid extensions: comparison of expressive power

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 HS. Although a number of HS fragments have been introduced and their computational complexity intensively studied, there is not much work on their expressive power. During the talk I will present my recent results aiming at filling this gap and enabling a better understanding of the interplay between computational complexity and expressive power of HS fragments. In particular, I will compare expressive power of Horn HS fragments with their hybrid extensions.