Kostas Stergiou, Manolis Koubarakis
We extend the framework of simple temporal problems studied originally by Dechter, Meiri and Pearl to consider constraints of the form x1 - y1 < or = r1 V...V xn - yn < or = rn; where x1...xn, y1...yn are variables ranging over the real numbers; r1...rn are real constants; and n < or = 1. We have implemented four progressively more efficient algorithms for the consistency checking problem for this class of temporal constraints. We have partially ordered those algorithms according to the number of visited search nodes and the number of performed consistency checks. Finally, we have carried out a series of experiments on the location of the hard region. The results show that the hard problems occur at a critical value of the ratio of disjunctions to variables. This value is between 6 and 7.