reddy@uiucdcs.CS.UIUC.EDU (06/02/86)
DFID can be viewed as an efficient implementation of Breadth-First search. It has relevance to single solution applications as well as multiple solution applications. For multiple solution applications, one naturally continues searching deeper levels even after one solution has been found. The solutions obtained by each search should be seen as increasingly better approximations to the set of all solutions: S0, S1, S2, ..... Sinfinity Whichever way it is used, it is naturally better than pure depth-first search, because it is complete whereas depth-first is not. Mark Stickel has implemented a theorem prover using a variant of DFID. See Stickel, A Prolog technology theorem prover, 1984 Intl symp on logic programming, Atlantic City. Stickel and Tyson, An analysis of consecutively bounded depth-first search with applications in automated deduction, (I think) IJCAI 85. Uday Reddy reddy@uiuc.arpa, uiucdcs!reddy