×

zbMATH — the first resource for mathematics

Match algorithms for generalized Rete networks. (English) Zbl 0762.68052
Summary: We present a match algorithm operates correctly on generalized Rete networks that allow arbitrary association of patterns.
We describe an abstract match algorithm for an abstract Rete network having additional edge memories, which provides a useful model for general Rete operations. We then develop two practical specializations of the abstract algorithm, and prove their correctness. The first specialization corresponds to traditional Rete match implementation techniques that are guaranteed to operate correctly for generalized Rete networks. The second specialization is formulated in a general way that allows for delaying match processing at arbitrary stop points within the Rete, with correct match results available on demand at a later time. One current system uses a derivative of this algorithm to support Rete-based matching on demand, complementing the normal match computations done on data-change.

MSC:
68T10 Pattern recognition, speech recognition
Keywords:
Rete match
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ART-IM programming language reference, (1989), Inference Corporation
[2] Brownston, L.; Farrell, R.; Kant, E.; Martin, N., ()
[3] Enhanced common LISP production system—user’s guide and reference (ECLPS), IBM publication no. SC38-7016, (1988)
[4] Forgy, C.L., OPS5 User’s manual, ()
[5] Forgy, C.L., Rete: a fast algorithm for the many pattern/many object pattern match problem, Artif. intell., 19, 17-37, (1982)
[6] Gupta, A., ()
[7] Knuth, D.E., (), 258-268
[8] Laird, J.E., SOAR User’s manual, (), Version 4, and addenda for version 4.4
[9] Lee, H.S.; Schor, M., Dynamic augmentation of generalized rete networks for demand-driven matching and rule updating, (), 123-129
[10] Miranker, D., TREAT: a better match algorithm for AI production systems, (), 42-47
[11] Miranker, D.; Lofaso, B., The organization and performance of a TREAT-based production system compiler, IEEE trans. knowl. data eng., 3, 1, 3-10, (1991)
[12] Scales, D., Efficient matching algorithms for the SOAR/OPS5 production system, (1986), Knowledge Systems Laboratory, Department of Computer Science, Stanford University Stanford, CA
[13] Schor, M.; Daly, T.; Lee, H.S.; Tibbitts, B., Advances in rete pattern matching, (), 226-232
[14] Tambe, M.; Kalp, D.; Gupta, A.; Forgy, C.L.; Milnes, B.; Newell, A., SOAR/PSM-E: investigating match parallelism in a learning production system, ACM SIGPLAN not., 23, 9, (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.