Previous: TR 92-18 Next: TR 92-20

Intellektik: Technical report 92-19

Search Space Pruning by Checking Dynamic Term Growth

Stefan Brüning

A method to detect non-terminating or failing queries based on analyzing the dynamic growth of terms is presented. It overcomes restrictions known from approaches to preclude infinite loops in the field of logic programming. The general idea is to predetermine what may happen to a term performing inference steps. Various well-known techniques and results of the theory of formal languages are used. The strength of our technique is emphasized by the fact that using it we are able to decide Horn-formulas consisting of facts, two-literal clauses, and a goal literal all of them restricted to unary predicate and unary function symbols.

Full Paper: Compressed postscript Compressed DVI

BibTeX entry