An intelligent backtracking algorithm for parallel execution of logic programs

Yow Jian Lin, Vipin Kumar, Clement Leung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

In this paper we present a simple but efficient backtracking scheme which works when AND-parallelism is exploited in a logic program. The scheme is well suited for implementation on a parallel hardware. We show that the backtracking scheme presented by Conery and Kibler in the context of AND/OR process model is incorrect, i.e., in some cases it may miss solutions while performing backtracking. Even if no AND-parallelism is exploited (i.e., all literals are solved sequentially), our scheme is more efficient than the "naive" depth-first backtracking strategy used by Prolog because our scheme makes use of the dependencies between literals in a clause. Chang and Despain have recently presented a backtracking scheme which also makes use of the dependencies between literals. We show that our scheme is more efficient than their scheme in the sense that our scheme does less backtracking.

Original languageEnglish (US)
Title of host publication3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings
EditorsEhud Shapiro
PublisherSpringer Verlag
Pages55-68
Number of pages14
ISBN (Print)9783540164920
DOIs
StatePublished - Jan 1 1986
Externally publishedYes
Event3rd International Conference on Logic Programming, ICLP 1986 - London, United Kingdom
Duration: Jul 14 1986Jul 18 1986

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume225 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Conference on Logic Programming, ICLP 1986
CountryUnited Kingdom
CityLondon
Period7/14/867/18/86

Fingerprint Dive into the research topics of 'An intelligent backtracking algorithm for parallel execution of logic programs'. Together they form a unique fingerprint.

Cite this