The Match Box algorithm for parallel production system match

Abstract: "We introduce Match Box, a new incremental matching algorithm for determining the tuple instantiations of forward-chaining production rules. Match Box is rooted in the mathematical interconnections between tuple and binding spaces, a framework also applicable to other matching algorithms. The idea is to precompute a rule's binding space, and then have each binding independently monitor working memory for the incremental formation of tuple instantiations. A key feature of Match Box is that on a massively parallel architecture, it can perform a rule's computationally intensive incremental joint testing in constant time. It also finds application on conventional serial processors."