[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #76 (Solved !)

Originator: Jean-Pierre Jouannaud
Date: June 1993

Summary: Is cycle unification decidable?

Cycle unification has been defined in [BHW92]. Is cycle unification decidable?

Remark

Cycle unification [BHW92] is undecidable [Dev93][HW93]. This was a long standing open problem, related to the non-termination of simple logic programs.

References

[BHW92]

Wolfgang Bibel, S. Hölldobler, and Jörg Würtz. Cycle unification. In Deepak Kapur, editor, 11th International Conference on Automated Deduction, volume 607 of Lecture Notes in Computer Science, pages 94–108, Saratoga Springs, NY, June 1992. Springer-Verlag.

[Dev93]

Phillipe Devienne. Personal communication, 1993.

[HW93]

Philipp Hanschke and Jörg Würtz. Satisfiability of the smallest binary program. Information Processing Letters, 45(5):237–241, April 1993.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]