Using rewriting techniques to solve the generalized word problem in polycyclic groups
Jürgen Avenhaus, D. Wi Gbmann · 1989
In this paper we apply rewriting techniques to the generalized word problem GWP in polycyclic groups. We assume the group G to be given by a canonical polycyclic string-rewriting system R and consider GWP in G which is defined by GWP(w,U) iff w∈ for w∈ G, finite U⊆G, where is the subgroup of G generated by U. We describe also by a rewrite system S and define a rewrite relation @@@@S,R in such a way that w @@@@S,R λ iff w∈ (λ the empty word). For this rewrite relation we develop different critical pair criteria for @@@@S,R to be λ-confluent, i.e. confluent on the left-congruence class [λ] of @@@@S,R. Using any of these λ-confluence criteria we construct a completion procedure which stops for every input S and computes a λ-confluent rewrite system equivalent to S. This leads to a decision procedure for GWP in G. Thus we give an explicit uniform algorithm for deciding GWP in polycyclic groups and a new proof based almost only on rewriting techniques for the decidability of this problem. Further, we define a rewrite relation @@@@LM,U which is stronger than @@@@S,R. We show that if G is given by a nilpotent string-rewriting system, then by a completion procedure the input U can be transformed into V such that @@@@LM,V is even confluent, not just λ-confluent.