Change search
ReferencesLink to record
Permanent link

Direct link
A complete classification of the expressiveness of interval logics of Allen’s relations: the general and the dense cases
Stockholm University, Faculty of Humanities, Department of Philosophy. University of Johannesburg, South Africa.ORCID iD: 0000-0002-0157-1644
Show others and affiliations
2016 (English)In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 53, no 3, 207-246 p.Article in journal (Refereed) Published
Abstract [en]

Interval temporal logics take time intervals, instead of time points, as their primitive temporal entities. One of the most studied interval temporal logics is Halpern and Shoham’s modal logic of time intervals HS, which associates a modal operator with each binary relation between intervals over a linear order (the so-called Allen’s interval relations). In this paper, we compare and classify the expressiveness of all fragments of HS on the class of all linear orders and on the subclass of all dense linear orders. For each of these classes, we identify a complete set of definabilities between HS modalities, valid in that class, thus obtaining a complete classification of the family of all 4096 fragments of HS with respect to their expressiveness. We show that on the class of all linear orders there are exactly 1347 expressively different fragments of HS, while on the class of dense linear orders there are exactly 966 such expressively different fragments.

Place, publisher, year, edition, pages
2016. Vol. 53, no 3, 207-246 p.
Keyword [en]
Interval temporal logic, Expressiveness, Bisimulation
National Category
Algebra and Logic
Research subject
Computer Science; Mathematical Logic; Theoretical Philosophy
URN: urn:nbn:se:su:diva-123441DOI: 10.1007/s00236-015-0231-4ISI: 000372894000001OAI: diva2:921811
Available from: 2016-04-21 Created: 2015-11-25 Last updated: 2016-04-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Goranko, Valentin
By organisation
Department of Philosophy
In the same journal
Acta Informatica
Algebra and Logic

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 100 hits
ReferencesLink to record
Permanent link

Direct link