Allen-Like Theory of Time for Tree-Like Structures

Allen’s Interval Algebra is one of the most prominent formalisms in the area of qualitative temporal (and, by extension, spatial) reasoning. However, its applications are naturally restricted to linear flows of time. While there is some recent work focusing on studying relations between intervals (and also between intervals and points) on branching structures, there is no rigourous study of the first-order theory of branching time. In this paper, we approach this problem under a very general definition of time structures, namely, tree-like lattices. While Allen’s work proved, over thirty years ago, that "meets" is expressively complete in the linear case, we prove here that, surprisingly, it remains complete for the class of all unbounded tree-like lattices. Such a result cannot be generalized 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 present a systematic study of minimally complete and maximally incomplete sets of relations, again, for both the unbounded and the general case, proving that while in the former case there are precisely four maximally incomplete and eight minimally complete sets, in the latter case these are, respectively, eight and nineteen.