Making exhaustive search programs deterministic

Kazunori Ueda*

*Corresponding author for this work

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

7 Citations (Scopus)


This paper presents a technique for compiling a Horn-clause program intended for exhaustive search into a GHC (Guarded Horn Clauses) program. The technique can be viewed also as a transformation technique for Prolog programs which compiles away the ‘bagof’ primitive and non-determinate bindings. The class of programs to which our technique is applicable is shown with a static checking algorithm; it is nontrivial and could be extended. An experiment on a compiler-based Prolog system showed that our technique improved the efficiency of exhaustive search by 6 times for a permutation generator program. This compilation technique is important also in that it exploits the AND-parallelism of GHC for parallel search.

Original languageEnglish
Title of host publication3rd International Conference on Logic Programming - Imperial College of Science and Technology, Proceedings
EditorsEhud Shapiro
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783540164920
Publication statusPublished - 1986
Externally publishedYes
Event3rd International Conference on Logic Programming, ICLP 1986 - London, United Kingdom
Duration: 1986 Jul 141986 Jul 18

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


Other3rd International Conference on Logic Programming, ICLP 1986
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Making exhaustive search programs deterministic'. Together they form a unique fingerprint.

Cite this