Generating, Storing and using the Complete Composition Table in Allen's Temporal Interval Algebra

T. Saulnier and A. Trudel (Canada)


Temporal reasoning, Allen’s 13 interval relations


A fundamental problem in temporal reasoning is the composition of two subsets of Allen relations to produce a third subset. Past research concentrated on clever algorithms and heuristics. Our proposed approach pre computes and caches all the results. This allows us to study properties of the results. We also experimentally compare our approach with previous algorithms and heuristics. Results show that for problems involving small networks, clever heuristics are useful. As network size increases, the cost of computing the heuristics becomes prohibitive. In this case, it is best to use our approach of a full composition table.

Important Links:

Go Back