scientific article; zbMATH DE number 3982556

From MaRDI portal
Publication:3746920





[For the entire collection see Zbl 0587.00020.] Typical PROLOG interpreters are essentially SLD refutation procedures. They are not complete because (among other causes) of the depth-first search strategy which can fail to find an actually successful but infinite computation path in the search tree. Pruning techniques are not complete and thus do not represent a solution. The proposed interpretation method can be considered as improved pruning technique and a generalization of the tabulation techniques for functional programs. (Tabulation prevents from repeatedly entering the evaluation of the same goal in a single computation path and from being trapped in an infinite path.) The conventional PROLOG interpreter is modeled by means of OLD refutation, which a special case of SLD refutation. An OLDT structure is a forest of partial OLD trees with two tables: the solution and the lookup table. Based on OLDT structure, the OLDT refutation is defined. As search strategy for the OLDT refutation the multistage depth-first strategy is chosen. (If no predicate is designated as table predicate, the multistage search for the OLDT refutation is exactly the depth-first search for OLD refutation.) Completeness (and termination for finite-model programs) is proved and comparison with the bottom up interpretation method is given. A major problem is to design optimal implementation techniques choosing the predicates that need not be designated as table predicates.




Cited in
(41)








This page was built for publication:

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