TEMPUS JEP3815 Workshop,
Budapest, Hungary, 1994

An Extension to the RETE Match Algorithm:
Supporting both Forward and Backward Chaining

Tamás Mészáros, Balázs Vadász
Technical University of Budapest,
Department of Measurement and Instrument Engineering
Budapest Hungary, H-1521, Műegyetem rkp 9.
tel. & fax: (36) 166-4938


Content areas:	Expert System Design, Integrating AI and Conventional Systems,
		Knowledge Representation

Abstract
The Rete match algorithm is widely accepted as one of the best solutions for
the many pattern/many object pattern matching problem [Forgy79]. It is mainly
applied in production systems to support the forward chaining inference. One of
its main advantages is that it saves state information between the forward
cycles. In every cycle only the working memory changes are processed. Moreover,
this algorithm exploits the structural redundancy of the rules.

However, it has some drawbacks. It does not allow the run-time change of the
rule base. It does not maintain a concentrated working memory. The working
memory elements are stored in the node memories of the Rete network. Finally,
the support for the backward chaining has not been worked out.

This paper presents a solution for this latest problem. It shows the extensions
needed to provide for the backward chaining operation on the same rule base.
The paper describes the detailed operation of the network during the backward
chaining. Based on the considerations presented in the paper a complete
inference engine has been implemented.