← All problems
Unverified
Can the application condition on the Merge rule in the computation of dag-solved forms of unification problems be improved?
The source page states the original problem together with its recorded qualifications and progress updates as follows.
Rules are given in [Jouannaud, 1991] for computing dag-solved forms of unification problems in equational theories. The Merge rule given there assumes that is not a variable and its size is less than or equal to that of . Can this condition be improved by replacing it with the condition that the rule Check* does not apply? (In other words, is Check* complete for finding cycles when Merge is modified as above?)
Recorded progress.
The problem has been solved by Hubert Comon [Jouannaud, 1991] using an extended Check rule (requiring a congruence closure step). The original question---for whatever it may be worth---stands.
