On Deciding Consistency for CSPs of Cyclic Time Intervals

May 2001

Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2001)

Volume

Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2001)

All Papers

We consider reasoning in an algebra of cyclic time intervals recently known in the literature; the algebra, CZ.A, is somehow the cyclic time counterpart of Allen’s algebra of linear time intervals, 1277.A. A composition table has been built for C24; the table can be used by a path consistency algorithm, such as Alien’s, to propagate knowledge expressed in the algebra as a constraint satisfaction problem (CSP). An important question which has not been answered so far is whether path consistency decides consistency for CZ.A atomic relations. We provide an example showing that the answer to the question is unfortunately negative: path consistency does not decide consistency for CZA atomic relations. We will then define an algebra of cyclic time points, C'P.A.. which, somehow, is for C what Vilain and Kautz’s linear time point algebra, 1277.A, is for 1277.4. C'PA is a subalgebra of CYCt, an algebra of ternary relations for cyclic ordering of 2D orientations also recently known in the literature. The pointisable part of CZA, i.e., the part one can translate into CPA, includes all atomic relations; from this, a complete solution search procedure for general CZ,4 CSPs derives, which uses results known for the algebra CYCt.