A data-dependency-based intelligent backtracking scheme for PROLOG

Vipin Kumar, Yow Jian Lin

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

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 languageEnglish (US)
Pages (from-to)165-181
Number of pages17
JournalThe Journal of Logic Programming
Volume5
Issue number2
DOIs
StatePublished - Jun 1988

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.

Fingerprint Dive into the research topics of 'A data-dependency-based intelligent backtracking scheme for PROLOG'. Together they form a unique fingerprint.

Cite this