On deciding consistency for CSPs of cyclic time intervals

We consider reasoning in an algebra of cyclic time inter-vals recently known in the literature; the algebra, CZ.A, is somehow the cyclic time counterpart of Allen’s al-gebra of linear time intervals, 1277.A. A composition table has been built for C2¢4; the table can be used by a path consistency algorithm, such as Alien’s, to propagate knowledge expressed in the algebra as a con-straint satisfaction problem (CSP). An important ques-tion which has not been answered so far is whether path consistency decides consistency for CZ.A atomic rela-tions. We provide an example showing that the answer to the question is unfortunately negative: path consis-tency does not decide consistency for CZA atomic re-lations. We will then define an algebra of cyclic time points, C’P.A.. which, somehow, is for C~-.A what Vi-lain and Kautz’s linear time point algebra, 127~.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 so-lution search procedure for general CZ,4 CSPs derives, which uses results known for the algebra CYCt