[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]


Problem #63 (Solved !)

Originator: Michio Oyamaguchi
Date: June 1993

Summary: Is confluence of right-ground term-rewriting systems decidable?

Is confluence of right-ground term-rewriting systems decidable? Compare [Oya87, DHLT90, DT90, OO93].

Remark

Related is [Oya90].

This has been solved positively by [GTV04].

References

[DHLT90]
Max Dauchet, Thierry Heuillard, Pierre Lescanne, and Sophie Tison. Decidability of the confluence of finite ground term rewriting systems and of other related term rewriting systems. Information and Computation, 88(2):187–201, October 1990.
[DT90]
Max Dauchet and Sophie Tison. The theory of ground rewrite systems is decidable. In John C. Mitchell, editor, Fifth Symposium on Logic in Computer Science, pages 242–248, Philadelphia, PA, June 1990. IEEE.
[GTV04]
Guillem Godoy, Ashish Tiwari, and Rakesh Verma. Characterizing Confluence by Rewrite Closure and Right Ground Term Rewrite Systems. Applicable Algebra in Engineering, Communication and Computing, 15(1):13–36, June 2004.
[OO93]
Michio Oyamaguchi and Yoshikatsu Ohta. On the confluent property of right-ground term rewriting systems. Trans. IEICE, J76-D-I:39–45, 1993.
[Oya87]
Michio Oyamaguchi. The Church-Rosser property for ground term rewriting systems is decidable. Theoretical Computer Science, 49(1):43–79, 1987.
[Oya90]
Michio Oyamaguchi. On the word problem for right-ground term-rewriting systems. In Trans. IEICE, volume E73-5, pages 718–723, 1990.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]