(To appear in Theory and Practice of Logic Programming (TPLP)) We introduce a systematic, concurrent execution scheme for Constraint Handling Rules (CHR) based on a previously proposed sequential goal-based CHR semantics. We establish strong correspondence results to the abstract CHR semantics, thus guaranteeing that any answer in the concurrent, goal-based CHR semantics is reproducible in the abstract CHR semantics. Our work provides the foundation to obtain efficient, parallel CHR execution schemes.
The most distinct characteristic of RETE is that partial matches are computed and stored. This and the eager nature of RETE matching is suitable for production rule systems as assertions (constraints) are propagated (not deleted) by default. Hence computing all matches rarely results in redundancy. Traditional CHR systems do not advocate this eager matching scheme because doing so results to many redundancies, due to overlapping simplified matching heads. Eager matching algorithms is also proved in @cite_11 to have a larger asymptotic worst-case space complexity than lazy matching algorithms.
@cite_11
2152631562
Production systems are an established method for encoding knowledge in an expert system. The semantics of production system languages and the concomitant algorithms for their evaluation, RETE and TREAT, enumerate the set of rule instantiations and then apply a strategy that selects a single instantiation for firing. Often rule instantiations are calculated and never fired. In a sense, the time and space required to eagerly compute these unfired instantiations is wasted. This paper presents preliminary results about a new match technique, lazy matching. The lazy match algorithm folds the selection strategy into the search for instantiations, such that only one instantiation is computed per cycle. The algorithm improves the worst-case asymptotic space complexity of incremental matching. Moreover, empirical and analytic results demonstrate that lazy matching can substantially improve the execution time of production system programs.