Abstract
This paper presents a scheme for intelligent backtracking in PROLOG programs. Rather than doing the analysis of unification failures, this scheme chooses backtrack points by doing the analysis of data dependency between literals. The other data-dependency-based methods previously developed cannot be easily incorporated in Warren's abstract machine, and are not able to perform across-the-clause backtracking intelligently. Our scheme overcomes all these defects. For many problems this scheme is just as effective as intelligent backtracking schemes based upon (more accurate) analysis of unification failure, and yet incurs small space and time over- head. To demonstrate the usefulness of our scheme, we have modified a simulator of Warren's abstract machine to incorporate our intelligent backtracking scheme, and have evaluated its performance on a number of problems.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 165-181 |
| Number of pages | 17 |
| Journal | The Journal of Logic Programming |
| Volume | 5 |
| Issue number | 2 |
| DOIs | |
| State | Published - Jun 1988 |
| Externally published | Yes |
Bibliographical note
Funding Information:*This work was supported by Army Research Office grant #DAAG29-84-K-0060 Intelligence Laboratory at the University of Texas at Austin. +Arpanet address: kumar@sally.UTEXAS.EDU. uucp: !harvard!ut-sally!kumar. Address correspondence to Dr. V. Kumar, Artificial Intelligence Laboratory, Department, University of Texas, Austin, Texas 78712-1188. Received December 1986; accepted August 1987.