Weak equivalence for constraint sets. (English) Zbl 0749.68018

Artificial intelligence, IJCAI-91, Proc. 12th Int. Conf., Sydney/Australia 1991, 851-856 (1991).
[For the entire collection see Zbl 0741.68016.]
In constraint solving systems, a typical input specification consists of a set of constraints and a set of restriction variables. The remaining variables in the set of constraints are intermediate variables, while the restriction variables are further divided in two mutually disjunct sets, namely known variables and wanted variables. In order to explicitly express the functional difference between wanted, known, and intermediate variables in a set of constraints, the authors introduce a more general equivalence, called weak equivalence, and its underlying notion of weak implication. Their formal properties are studied in the context of sound and complete axiom systems provided in the paper. Based on the new defined notions of weak equivalence and implication, the constraint solver can be guided towards a solution that discards intermediate variables and expresses wanted variables in terms of known variables. The derivation of symbolic relationships is done by two processes:
(1) weak equivalence allows to express formally the correspondence between the derived relationship and the original constraint set, and
(2) the reasoning necessary for inference of symbolic relationships can be represented in terms of weak equivalence.
The run examples, motivated by the role of weak equivalence in the integration of relational databases and constraint solving, are using in the declarative rule language RL, due to P. van Emde Boas [Lect. Notes Comput. Sci. 233, 78-92 (1986; Zbl 0619.68032)], and proved the practical applicability of weak equivalence for constraint solving purposes.
Reviewer: N.Curteanu (Iaşi)


68N17 Logic programming
68T99 Artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)