Making exhaustive search programs deterministic

DOI10.1007/BF03037456MaRDI QIDQ1094889zbMATH OpenFDO

Authors Kazunori Ueda

Publication date 1987

Published in New Generation Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF03037456

zbMATH Keywords

compilationexhaustive searchHorn-clause programmultiple binding environmentsparallelismprogram transformationProlog programs

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 41233
• scientific article; zbMATH DE number 773980
• scientific article; zbMATH DE number 4074449
• \textsc{Tor}: modular search with hookable disjunction
• scientific article; zbMATH DE number 4058911

Cites work

• scientific article; zbMATH DE number 3872640 (Why is no real title available?)
• scientific article; zbMATH DE number 4074449 (Why is no real title available?)
• scientific article; zbMATH DE number 41233 (Why is no real title available?)
• Notes on the implementation of PARLOG
• PARLOG: parallel programming in logic

Cited in

(5)

• Existential continuation
• \textsc{Tor}: modular search with hookable disjunction
• scientific article; zbMATH DE number 41233 (Why is no real title available?)
• scientific article; zbMATH DE number 7047281 (Why is no real title available?)
• First order compiler: A deterministic logic program synthesis algorithm

Describes a project that uses

Uses Software

• PARLOG
• GHC

This page was built for publication: Making exhaustive search programs deterministic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1094889)