Optimal union-find in Constraint Handling Rules

TOM SCHRIJVERS; THOM FRÜHWIRTH

doi:10.1017/S1471068405002541

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Betz, Hariolf and Frühwirth, Thom 2005. Principles and Practice of Constraint Programming - CP 2005. Vol. 3709, Issue. , p. 137.

Schrijvers, Tom Demoen, Bart Duck, Gregory Stuckey, Peter and Frühwirth, Thom 2006. Automatic Implication Checking for CHR Constraints. Electronic Notes in Theoretical Computer Science, Vol. 147, Issue. 1, p. 93.

De Koninck, Leslie Schrijvers, Tom and Demoen, Bart 2007. Logic Programming. Vol. 4670, Issue. , p. 209.

Meister, Marc Djelloul, Khalil and Robin, Jacques 2007. Logic Programming and Nonmonotonic Reasoning. Vol. 4483, Issue. , p. 201.

Meister, Marc Djelloul, Khalil and Frühwirth, Thom 2007. Recent Advances in Constraints. Vol. 4651, Issue. , p. 139.

De Koninck, Leslie Schrijvers, Tom and Demoen, Bart 2007. User-definable rule priorities for CHR. p. 25.

Wolf, Armin Robin, Jacques and Vitorino, Jairson 2008. Constraint Handling Rules. Vol. 5388, Issue. , p. 48.

Frühwirth, Thom 2008. Recent Advances in Constraints. Vol. 5129, Issue. , p. 91.

De Koninck, Leslie Stuckey, Peter J. and Duck, Gregory J. 2008. Functional and Logic Programming. Vol. 4989, Issue. , p. 32.

Sneyers, Jon Schrijvers, Tom and Demoen, Bart 2009. The computational power and complexity of constraint handling rules. ACM Transactions on Programming Languages and Systems, Vol. 31, Issue. 2, p. 1.

Djelloul, Khalil 2009. From exponential to almost linear decomposability of finite or infinite trees. p. 897.

SNEYERS, JON VAN WEERT, PETER SCHRIJVERS, TOM and DE KONINCK, LESLIE 2010. As time goes by: Constraint Handling Rules. Theory and Practice of Logic Programming, Vol. 10, Issue. 1, p. 1.

Afek, Yehuda Avni, Hillel and Shavit, Nir 2011. Principles of Distributed Systems. Vol. 7109, Issue. , p. 65.

Hanus, Michael 2015. Practical Aspects of Declarative Languages. Vol. 9131, Issue. , p. 74.

Frühwirth, Thom 2018. Declarative Programming and Knowledge Management. Vol. 10997, Issue. , p. 37.

SCHRIJVERS, TOM VAN DEN BERG, BIRTHE and RIGUZZI, FABRIZIO 2023. Automatic Differentiation in Prolog. Theory and Practice of Logic Programming, Vol. 23, Issue. 4, p. 900.

Article contents

Optimal union-find in Constraint Handling Rules

Abstract

Keywords

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Article contents

Optimal union-find in Constraint Handling Rules

Abstract

Keywords

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests