Temporal reasoning plays an essential role in many applications. Two common paradigms for reasoning about temporal constraints are based on Allen’s interval algebra [1] and point algebra [2]. The computational behavior of the two formalisms has been thoroughly studied. The paper continues this kind of investigation by proposing novel algorithms for classes of polynomial constraints where the set of constraints is given incrementally. The worst-case complexity of the algorithms is studied, and it is shown that the restriction on incremental constraints results in a speedup with respect to the general (nonincremental) best-known complexity results. In addition, for some classes of constraints, conditions are given under which the general algorithms can be replaced by the incremental algorithms. The theoretical results have been validated by experiments.

The paper is rather technical, and it is mainly directed to an audience familiar with temporal constraints and communicating sequential processes. The presentation is clear, even though it very often assumes a specific background in the field.