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.