An improved version of the many-pattern, many-object pattern matching algorithms for Rete networks is presented. Starting from the idea that existing versions of match algorithms for generalized Rete networks may induce errors in computing some match results, the authors present two match algorithms that behave correctly in all cases, including arbitrarily grouped joins of patterns and self-joined nodes.
An abstract match algorithm is first described, which provides a model for general Rete operations and enables the correctness proofs. Two practical specializations of this algorithm are then presented. The first algorithm performs correctly on generalized Rete networks and eliminates the space inefficiencies of the abstract algorithm. The second algorithm extends the first for correct update operations from multiple predecessor nodes. Descriptive proofs of correctness are given for all algorithms. The authors state that the two practical algorithms are implemented in Enhanced Common Lisp Production System.
The purpose of this presentation of the research, which has already been realized in a working implementation, is the description of the algorithms, but the authors emphasize the correctness of the approach. The paper is intended for specialists who are already acquainted with Rete algorithms. For readers without this background, the material is difficult to understand because many new terms are not fully explained. One of the best features of the paper is the citation of other related work, as compared with the proposed solutions, but no weaknesses of the approach are mentioned.