On binary constraint problems. (English) Zbl 0813.03045

The authors generalize the concepts of binary constraint satisfaction problems to Tarski’s relation algebras. Algorithms for path-consistency can be implemented on matrices of relations and on matrices of elements from a relation algebra. The authors give an example of a \(4\times 4\) matrix of infinite relations on which no iterative local path consistency algorithm terminates. Further, a class of examples over a fixed finite algebra are given on which all iterative local algorithms (sequential as well as parallel) must take quadratic time. Specific relation algebras arising from interval constraint problems are also studied.
Reviewer: C.Meinel (Trier)


03G15 Cylindric and polyadic algebras; relation algebras
68Q25 Analysis of algorithms and problem complexity
68T30 Knowledge representation
Full Text: DOI