A PROLOG TECHNIQUE OF IMPLEMENTING SEARCH OF A O GRAPHS WITH CONSTRAINTS/

Our research has been motivated by the task of forming a solution subg raph which satisfies given constraints. The problem is represented by an A/O graph. Our approach is to apply a suitably modified technique o f dependency-directed backtracking. We present our formulation of the standard chronological backtracking algorithm in Prolog. Based on it, we have developed an enhanced algorithm which makes use of special heu ristic knowledge. It involves also the technique of node marking. We h ave gathered experience with the prototype Prolog implementation of th e algorithm in applying it to (one step of) the problem of building a software configuration. Our experience shows that Prolog programming t echniques offer a considerable flexibility in implementing the above o utlined tasks.