Dynamic Programming, Integral Polyhedra and Horn Clause Knowledge Base
R. G. Jeroslow, Jinchang Wang · INFORMS journal on computing · 1989
We show how the structure of proofs in a Horn clause knowledge base is completely described by certain of the extreme solutions to a suitable “dual” linear constraint set. The extreme points of this linear system are integer vectors, and give the count of the number of times that a given proposition is used in a proof of a “target” proposition. The “primal” to this dual provides the pointwise maximum vector which solves a set of dynamic programming recursions, and the latter recursions are derived from the Horn clause knowledge base. Variation in the facts or in the rules of the knowledge base corresponds to changes in only the criterion vector of the dual linear program. This linear programming approach to inference in expert systems also allows for the detection of “near proofs.” The latter are, by definition, proof structures which would become valid, if only exactly one more fact were known to be true. The first author, Robert G. Jeroslow, deceased August 31, 1988. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.