← 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 x≈s,x≈t⇒x≈s,s≈tx \approx s,x \approx t \Rightarrow x \approx s,s \approx t given there assumes that ss is not a variable and its size is less than or equal to that of tt. 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.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu