Robin Hirsch

Propagation terminates over a finite set of binary constraints, even if the binary relations generate an infinite set of relations

We consider constraint networks where the binary constraints come from a possibly infinite set of binary relations. We show that a run of the propagation algorithm on a finite constraint network can fail to terminate. However, we show that on any finite constraint network there is a run of the propagation algorithm that terminates in O(n⁴) time, where n is the number of nodes of the constraint network. We generalise to k-ary relations, for k>2, and show that non-terminating runs for k-ary constraint networks exist, but also on any k-ary constraint network there is a terminating run of the propagation algorithm of length at most kn^k+(n+1)n^2k.