Making exhaustive search programs deterministic

Kazunori Ueda*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 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
Pages (from-to)29-44
Number of pages16
JournalNew Generation Computing
Issue number1
Publication statusPublished - 1987 Mar 1
Externally publishedYes


  • Compilation
  • Continuation
  • Exhaustive Search
  • Guarded Horn Clauses
  • Mode Analysis
  • Multiple Binding Environments
  • Parallelism
  • Program Transformation

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications


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

Cite this