Expressiveness of the Interval Logics of Allen's Relations on the Class of All Linear Orders: Complete Classification

Della Monica, Dario; Goranko, Valentin; Montanari, Angelo; Sciavicco, Guido

doi:10.5591/978-1-57735-516-8/IJCAI11-147

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, Guido Sciavicco

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 845-849.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-147

Abstract

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 inter-definability 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.

Dario Della Monica, Valentin Goranko, Angelo Montanari, and Guido Sciavicco. 2011. Expressiveness of the Interval Logics of Allen's Relations on the Class of All Linear Orders: Complete Classification. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 845–849. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-147

@inproceedings{ijcai2011p147,
  title     = {Expressiveness of the Interval Logics of Allen's Relations on the Class of All Linear Orders: Complete Classification},
  author    = {Della Monica, Dario and Goranko, Valentin and Montanari, Angelo and Sciavicco, Guido},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {845--849},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-147},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-147},
}

TY  - CPAPER
TI  - Expressiveness of the Interval Logics of Allen's Relations on the Class of All Linear Orders: Complete Classification
AU  - Della Monica, Dario
AU  - Goranko, Valentin
AU  - Montanari, Angelo
AU  - Sciavicco, Guido
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 845
EP  - 849
DO  - 10.5591/978-1-57735-516-8/IJCAI11-147
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-147
ER  -