Expressiveness of the Interval Logics of Allen’s Relations on the Class of all Linear Orders: Complete Classification
Dario Della Monica, Valentin Goranko, Angelo Montanari and Guido Sciavicco
This paper compares the expressiveness of the fragments of Halpern and Shoham's interval logic HS, i.e., of all interval logics with modal operators associated with Allen's relations between intervals in linear orders. We establish a complete set of inter-definability equations between these modal operators, and thus obtain a complete classification of the family of $2^{12}$ fragments of HS with respect to their expressiveness. Using that result and a computer program, we have found that there are 1347 expressively different such interval logics over the class of all linear orders.