OFAI

Technical Reports - Query Results

Your query term was 'number = 90-11'
1 report found
OFAI-TR-90-11 ( 156kB g-zipped PostScript file)

Realization of Forward Checking in Logic Programming via Extended Unification

Christian Holzbaur

Forward checking is one of the most promising a priori pruning techniques for Constraint Satisfaction Problems (Mackworth 1977, Mackworth and Freuder 1985). In the past some schemes for the incorporation of forward checking and other consistency techniques over finite domains into Prolog have been introduced in (Hentenryck 1989). This work resulted in the implementation of a new prototype Prolog interpreter. In this paper we present an implementation of forward checking in Prolog. This implementation is based on a very general scheme for the incorporation of semantic unification into Prolog (Holzbaur 1990, Neumerkel 1990). Constraint Satisfaction Problems can be formulated declaratively in Prolog. The problem with the standard backtracking evaluation strategy however is that it does not execute this specification efficiently. Therefore, the Prolog implementation of forward checking serves at least two purposes: the set of effectively executable declarative specifications in Prolog is enlarged; the choice of Prolog as implementation language results in more declarative, reliable, maintainable, accessible, and extendible code.

Citation: Holzbaur C.: Realization of Forward Checking in Logic Programming via Extended Unification, Austrian Research Institute for Artificial Intelligence, Vienna, TR-90-11, 1990.