Match algorithms for generalized Rete networks

摘要

We present a match algorithm which operates correctly on generalized Rete networks that allow arbitrary association of patterns. The original OPS5 Rete algorithm implements matching for left-associative joins; later work generalized this algorithm to support arbitrary join association. However, the naive extension of the OPS5 Rete algorithm to support arbitrary join associations has some subtle flaws (sometimes not all matches are produced with no duplicates) when processing networks having reconvergent (or self-joined) nodes.