Author:

Keywords:

Constraint Handling Rules, Optimization, Propagation rules, Science & Technology, Technology, Computer Science, Artificial Intelligence, Computer Science, Theory & Methods, Computer Science, CONSTRAINT HANDLING RULES

Abstract:

Constraint Handling Rules (CHR) is an elegant, high-level programming language based on multi-headed, forward chaining rules. To ensure CHR propagation rules are applied at most once with the same combination of constraints, CHR implementations maintain a so-called propagation history. The performance impact of this history can be significant. We introduce several optimizations that, for the majority of CHR rules, eliminate this overhead. We formally prove their correctness, and evaluate their implementation in two state-of-the-art CHR systems.