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

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2011

View graph of relations

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.
Original languageEnglish
TitleProceedings of the Twenty-Second International Joint Conference on Artificial Intelligence
Publication date2011
Pages845-850
StatePublished

Conference

ConferenceInternational Joint Conference on Artificial Intelligence
Number22
CityBarcelona, Spain
Period01/01/11 → …
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 6302062