Derivation of an Efficient Rule System Pattern Matcher

Title: en_US Derivation of an Efficient Rule System Pattern Matcher
Creator: en_US Wertheimer, Jeremy M.
Date: 2004-10-20T20:12:04Z
Date Available: 2004-10-20T20:12:04Z
Date Issued: en_US 1989-02-01
Identifier: en_US AITR-1109
uri: http://hdl.handle.net/1721.1/6979
Abstract: en_US Formalizing algorithm derivations is a necessary prerequisite for developing automated algorithm design systems. This report describes a derivation of an algorithm for incrementally matching conjunctive patterns against a growing database. This algorithm, which is modeled on the Rete matcher used in the OPS5 production system, forms a basis for efficiently implementing a rule system. The highlights of this derivation are: (1) a formal specification for the rule system matching problem, (2) derivation of an algorithm for this task using a lattice-theoretic model of conjunctive and disjunctive variable substitutions, and (3) optimization of this algorithm, using finite differencing, for incrementally processing new data.
Extent: 9034855 bytes; 3382405 bytes
Format: application/postscript; application/pdf
Language: en_US
Relation: en_US AITR-1109