DFKI Technical Memo-94-02
by Rainer Bleisinger, Berthold Kröll
Representation of Non-Convex Time Intervals and Propagation of Non-Convex Relations
For representing natural language expressions with temporal repetition the well known time interval calculus of Allen [Allen 83] is not adequat. The fundamental concept of this calculus is that of convex intervals which have no temporal gaps. However, natural language expressions like "every Summer" or "on each Monday" require the possibility of such temporal gaps.
Therefore, we have developed a new calculus based on non-convex intervals and have defined a set of corresponding non-convex relations. The non-convex intervals are sets of convex intervals and contain temporal gaps. The non-convex relations are tripels: a first part for specifying the intended manner of the whole relation, a second part for defining relations between subintervals, and a third part for declaring relations of whole, convexified non-convex intervals. In the non-convex calculus the convex intervals and relations of Allen are also integrated as a special case.
Additionally, we have elaborated and fully implemented a constraint propagation algorithm for the non-convex relations. In comparison with the convex case we get a more expressive calculus with same time complexity for propagation and only different by a constant factor.
This document is available as Postscript.
The next abstract is here, and the previous abstract is here.
Note: This page was written to look best with CSS stylesheet support Level 1 or higher. Since you can see this, your browser obviously doesn't support CSS, or you have turned it off. We highly recommend you use a browser that supports and uses CSS, and review this page once you do. However, don't fear, we've tried to write this page to still work and be readable without CSS.