Interval temporal logics provide a natural framework for temporal
reasoning about interval structures over linearly
ordered domains, where intervals are taken as first-class
citizens. Their expressive power and computational behaviour
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 rationals,
and we provide a complete classification of them in
terms of their expressiveness and computational complexity by solving the last few
open problems.
