We compare 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 interdefinability equations between these modal operators, and thus obtain a complete classification of the family of 212 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.
|Title of host publication||Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence|
|Publication status||Published - 2011|
|Event||22nd International Joint Conference on Artificial Intelligence - Barcelona, Spain|
Duration: 16 Jul 2011 → 22 Jul 2011
Conference number: 22
|Conference||22nd International Joint Conference on Artificial Intelligence|
|Period||16/07/2011 → 22/07/2011|