CW 389

Tom Schrijvers and Thom Fruehwirth
Implementing and Analysing Union-Find in CHR

Abstract

CHR is a committed-choice rule-based language that was originally intended for writing constraint solvers. In this paper we show that it is also possible to write the classic union-find algorithm and variants in CHR. The programs neither compromise in declarativeness nor efficiency. Using CHR analysis techniques we study logical correctness, confluence and time complexity of our programs. We observe the essential destructive update of the algorithm. We can match the time complexity of the best known imperative implementations with the help of hashtable indexes. We illustrate the fact with experimental results.

Related material is available in the online appendix.