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 language||English (US)|
|Title of host publication||3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings|
|Number of pages||14|
|State||Published - 1986|
|Event||3rd International Conference on Logic Programming, ICLP 1986 - London, United Kingdom|
Duration: Jul 14 1986 → Jul 18 1986
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||3rd International Conference on Logic Programming, ICLP 1986|
|Period||7/14/86 → 7/18/86|
Bibliographical noteFunding Information:
This work was supported by Army Research Office grant #DAAG29-84-K-0060 to the Artificial Intelligence Laboratory at the University of Texas at Austin.
© 1986, Springer-Verlag.
Copyright 2017 Elsevier B.V., All rights reserved.