Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6873861 | Information and Computation | 2018 | 15 Pages |
Abstract
Allen's Interval Algebra is among the leading formalisms in the area of qualitative temporal reasoning. However, its applications are restricted to linear flows of time. While there is some recent work studying relations between intervals on branching structures, there is no rigorous study of the first-order theory of branching time. In this paper, we approach this problem under a general definition of time structures, namely, tree-like lattices. Allen's work proved that meets is expressively complete in the linear case. We also prove that, surprisingly, it remains complete for all unbounded tree-like lattices. This does not generalize to the case of all tree-like lattices, for which we prove that the smallest complete set of relations has cardinality three. We provide in this paper a sound and complete axiomatic system for both the unbounded and general case, in Allen's style, and we classify minimally complete and maximally incomplete sets of relations.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
S. Durhan, G. Sciavicco,