A test for λ-confluence for certain prefix rewriting systems with applications to the generalized word problem
N. Kuhn, Klaus Madlener, Friedrich Otto · 1990
We apply rewriting techniques to the generalized word problem for groups. Let R be a finite string-rewriting system on an alphabet Σ such that the monoid MR presented by (Σ:R) is a group, and let U ⊆ Σ→ be a finite set. The generalized word problem GWP is defined by GWP(w.U) if w ∈ , where is the subgroup of MR generated by U. With U we associate a prefix rewriting relation ⇒P on Σ* such that w P λ if GWP(w.U) holds. If ⇒P is λ-confluent then w ⇒ P λ if w ∈ . Then ⇒P yields a decision procedure for GWP. For groups given through confluent string-rewriting systems R, we develop a necessary and sufficient condition for ⇒P being λ-confluent and show that this condition becomes decidable in case of R being length-reducing, in addition.