(15) Incorporating Linear-Space Best-First Search in MGTP

MGTP has been widely used as a theorem prover for full first-order logic. However, for purposes other than theorem proving, MGTP has been less used. In particular, the methodology for non-Horn clause programming has not been well developed as compared with Horn clause logic programming. In this research, to expand the application range of MGTP, we incorporate search based on costs into MGTP. First, we introduce the depth-first iterative-deepening (DFID) search into MGTP in order to improve the termination of MGTP. Next, we propose a general programming language in the form of disjunctive logic programs with costs. Then, to apply MGTP to optimization problems, we incorporate a new search algorithm into MGTP with a best-first iterative-deepening (BFID) method, which deals with problems with costs. Finally, we apply Non-Horn Magic Sets (NHM) method in order to increase the efficiency of optimization problems. Using NHM, we can restrict the search space in bottom-up reasoning only to subgoals that are related to the given goal.

Research Period :	June 1997 - February 1998
Cooperate Researchers :	Hiromasa Haneda Kobe Univ. Jun-ichi Sekiyama Toyohashi Univ. of Technology Hidetomo Nabeshima Toyohashi Univ. of Technology Ryuzo Hasegawa Kyushu Univ. , Professor