Schedulers and Redundancy for a Class of Constraint Propagation Rules

Title: Schedulers and Redundancy for a Class of Constraint Propagation Rules

Abstract: This research study focuses on developing efficient schedulers for a specific class of rules called proprules, which naturally arise in the context of rule-based constraint programming. The authors introduce an abstract framework for scheduling and instantiate it with specific partial orderings and functions to obtain a scheduler called R. They demonstrate the effectiveness of this approach by implementing it for membership rules, a crucial class of proprules. The implementation significantly outperforms the standard implementation of membership rules in the CHR language, highlighting the practical benefits of studying constraint propagation on an abstract level. Additionally, the research clarifies how to identify and reduce redundant proprules, providing a semantic approach to redundancy.

Main Research Question: How can we develop efficient schedulers for a class of constraint propagation rules called proprules?

Methodology: The study uses an abstract framework for scheduling based on a generic iteration algorithm on partial orderings. This framework is instantiated with specific partial orderings and functions to obtain the R algorithm, a scheduler for proprules. The implementation is tested with membership rules, a crucial class of proprules.

Results: The implementation outperforms the standard implementation of membership rules in the CHR language, demonstrating the effectiveness of the developed scheduler. The research also provides insights into identifying and reducing redundant proprules.

Implications: The research has practical implications for the development of efficient constraint programming systems. By studying constraint propagation on an abstract level, the study provides a general approach to scheduling that can be applied to various classes of rules. The semantic approach to redundancy can also be useful in other areas of computer science where redundancy needs to be identified and managed.

Link to Article: https://arxiv.org/abs/0403037v1 Authors: arXiv ID: 0403037v1