(7) Fast Hypothetical Reasoning System

[Software Features]

     This program provides a predicate-logic version of fast 
cost-based hypothetical reasoning based on the Networked Bubble 
Propagation (NBP) method. (More precisely, this program can deal with 
range-restricted function-free Horn clauses.)  While the computation 
time for cost-based hypothetical reasoning grows exponentially in 
general with respect to problem size, this program can compute a good 
near-optimal solution in low-order polynomial time.

     The NBP method, originally developed based on a 
pivot-and-compliment method, is an efficient approximate solution 
method for 0-1 integer programming.  By replacing pivoting and other 
operations in the pivot-and-compliment method with network-based 
operations and by using the knowledge network structure, the NBP 
method achieves high inference efficiency.  The NBP method's 
propositional-logic version achieves approximately 1.5-order of 
polynomial time with respect to the number of possible element 
hypotheses.     

     Although an extended NBP method for handling predicate-logic 
knowledge was developed before, this predicate-logic version, NBP2a, 
is implemented with a different and rather simple approach.  This 
program uses the QSQR method, an efficient deductive database method, 
in an iterative deepening manner to produce a series of sub-problems of 
propositional-logic hypothetical reasoning, which can be solved 
efficiently through the NBP method of propositional-logic version.      

[Required Environment]

Standard C compiler and a X-window software tool
  (for compiling nbp1b.c to produce nbp).

Sicstus Prolog (for qsqr.plg).

Pearl Interpreter.

[File Configuration]

nbp1b.c: A propositional-logic version of the NBP method written in C for
         cost-based hypothetical reasoning. [73KB]

{nbp:    An executable program produced by compiling nbp1b.c with a C
         compiler and an X-window software tool as follows;
                gcc nbp1b.c -1X11 -lm -0 nbp }

qsqr.plg: A Sicstus Prolog program for transforming a predicate-logic
         hypothetical reasoning problem into a series of propositional-logic 
         sub-problems in an iterative deepening manner. [3.5KB]

runqsqr: A Pearl program to perform smooth data exchange between
         qsqr.plg and nbp (a propositional-logic version of NBP method).
         [5.6KB]


Sicstus Prolog is required for executing qsqr.plg. A Pearl interpreter is 
required for runqsqr.                                                        

[FTP]

• README
• Program and Documents in Japanese [46.2K]