An intelligent backtracking algorithm for parallel execution of logic programs

Yow Jian Lin; Vipin Kumar; Clement Leung

doi:10.1007/3-540-16492-8_64

An intelligent backtracking algorithm for parallel execution of logic programs

Yow Jian Lin, Vipin Kumar, Clement Leung

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

12 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 language	English (US)
Title of host publication	3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings
Editors	Ehud Shapiro
Publisher	Springer Verlag
Pages	55-68
Number of pages	14
ISBN (Print)	9783540164920
DOIs	https://doi.org/10.1007/3-540-16492-8_64
State	Published - 1986
Externally published	Yes
Event	3rd International Conference on Logic Programming, ICLP 1986 - London, United Kingdom Duration: Jul 14 1986 → Jul 18 1986

Publication series

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

Other

Other	3rd International Conference on Logic Programming, ICLP 1986
Country/Territory	United Kingdom
City	London
Period	7/14/86 → 7/18/86

Bibliographical note

Funding 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.

Publisher Copyright:
© 1986, Springer-Verlag.

Publisher link

10.1007/3-540-16492-8_64

Find It

Find It at U of M Libraries

Cite this

Lin, Y. J., Kumar, V., & Leung, C. (1986). An intelligent backtracking algorithm for parallel execution of logic programs. In E. Shapiro (Ed.), 3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings (pp. 55-68). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 225 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-16492-8_64

An intelligent backtracking algorithm for parallel execution of logic programs. / Lin, Yow Jian; Kumar, Vipin; Leung, Clement.
3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings. ed. / Ehud Shapiro. Springer Verlag, 1986. p. 55-68 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 225 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lin, YJ, Kumar, V & Leung, C 1986, An intelligent backtracking algorithm for parallel execution of logic programs. in E Shapiro (ed.), 3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 225 LNCS, Springer Verlag, pp. 55-68, 3rd International Conference on Logic Programming, ICLP 1986, London, United Kingdom, 7/14/86. https://doi.org/10.1007/3-540-16492-8_64

Lin YJ, Kumar V, Leung C. An intelligent backtracking algorithm for parallel execution of logic programs. In Shapiro E, editor, 3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings. Springer Verlag. 1986. p. 55-68. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-16492-8_64

Lin, Yow Jian ; Kumar, Vipin ; Leung, Clement. / An intelligent backtracking algorithm for parallel execution of logic programs. 3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings. editor / Ehud Shapiro. Springer Verlag, 1986. pp. 55-68 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{82ddfe0ac09b4884b04df8327ac8c1cd,

title = "An intelligent backtracking algorithm for parallel execution of logic programs",

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.",

author = "Lin, {Yow Jian} and Vipin Kumar and Clement Leung",

note = "Funding 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. Publisher Copyright: {\textcopyright} 1986, Springer-Verlag.; 3rd International Conference on Logic Programming, ICLP 1986 ; Conference date: 14-07-1986 Through 18-07-1986",

year = "1986",

doi = "10.1007/3-540-16492-8_64",

language = "English (US)",

isbn = "9783540164920",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "55--68",

editor = "Ehud Shapiro",

booktitle = "3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings",

}

TY - GEN

T1 - An intelligent backtracking algorithm for parallel execution of logic programs

AU - Lin, Yow Jian

AU - Kumar, Vipin

AU - Leung, Clement

N1 - Funding 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. Publisher Copyright: © 1986, Springer-Verlag.

PY - 1986

Y1 - 1986

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85034455726&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034455726&partnerID=8YFLogxK

U2 - 10.1007/3-540-16492-8_64

DO - 10.1007/3-540-16492-8_64

M3 - Conference contribution

AN - SCOPUS:85034455726

SN - 9783540164920

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 55

EP - 68

BT - 3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings

A2 - Shapiro, Ehud

PB - Springer Verlag

T2 - 3rd International Conference on Logic Programming, ICLP 1986

Y2 - 14 July 1986 through 18 July 1986

ER -

An intelligent backtracking algorithm for parallel execution of logic programs

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this