Boolean constraints in SICStus Prolog

Carlsson, Mats (1991) Boolean constraints in SICStus Prolog. [SICS Report]



This report documents the implementation of a Boolean constraint solver and its integration with a Prolog engine. The solver comprises built-in predicates for checking consistency and entailment of a new constraint w.r.t. accumulated constraints and for generating particular solutions to a set of constraints, and extensions to the Prolog top-level for displaying answer constraints. Boolean unification was chosen as the strategy for the consistency check. Boolean unification fits well with the Prolog execution model, and allows the accumulated constraints to be associated in a natural way with the variables being eliminated. The answer constraints are computed by existentially quantifying in the accumulated set of constraints all variables not occurring in the user query. The simplified set of constraints constitutes the answer constraints. Boolean formulas are internally represented as DAGs. Details are provided on this representation and the support for it provides by Prolog Engine. We have investigated various optimizations of the Boolean unification algorithm, and a preliminary performance evaluation is included.

Item Type:SICS Report
ID Code:2485
Deposited By:Vicki Carleson
Deposited On:29 Apr 2009
Last Modified:18 Nov 2009 16:09

Repository Staff Only: item control page