Design a framework for combining constraint solving algorithms.

The source page states the original problem together with its recorded qualifications and progress updates as follows.

Design a framework for combining constraint solving algorithms.

Recorded progress.

Some particular cases have been attacked: In [Jouannaud, 1991] it was shown how decision procedures for solvability of unification problems can be combined. In [Jouannaud, 1991] a similar technique is applied to (unquantified) systems of equations and disequations. In [Jouannaud, 1991] the combination of unification algorithms is extended to the case where alphabets share constants. In related work [Jouannaud, 1991], unification is performed in the combination of an equational theory and membership constraints.

Some further progress is in [Jouannaud, 1991].

The combination approach of [Jouannaud, 1991] has been extended in [Jouannaud, 1991] to constraints involving predicate symbols other that equality, and [Jouannaud, 1991] in turn extends this approach to constraint-solving over solution domains that are not free structures. These results are presented in a uniform framework by [Jouannaud, 1991].

The work of [Jouannaud, 1991] has been extended to the case of ``shared constructors'' by~[Jouannaud, 1991].

Recorded update.

Submitted by Miki Hermann on Mon Apr 27 12:05:20 MET DST 1998.

Unification algorithms (and therefore also constraint solvers) cannot be combined in polynomial time, as proved by Hermann and Kolaitis in~[Jouannaud, 1991].