2005/01/25 by Tom Schrijvers, Schrijvers, Tom, Thom Fruehwirth +1
Computer Science · #AI-based Problem Solving and Planning #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Model-Driven Software Engineering Techniques #Performance (cs.PF) #Programming Languages (cs.PL) #cs.CC #cs.DS #cs.PF #cs.PL
paper · pdf · doi:10.48550/arxiv.cs/0501073
12 pages, 3 figures, to appear in Theory and Practice of Logic Programming (TPLP)
arxiv created 2005/01/25 · openalex publication_date 2005/01/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Constraint Handling Rules (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. We study the time complexity of our programs: they match the almost-linear complexity of the best known imperative implementations. This fact is illustrated with experimental results.