8. Appendix

In this section we show that polycyclic groups have reversed polycyclic power commutation presentations which are convergent with respect to a syllable ordering with status right.

Let ${\cal G}$ be a polycyclic group with $(\Sigma, T)$ a convergent PCP-system as described in section 2. For the set of rules T we define $\rho(T) = \{ \rho(l) \longrightarrow\rho(r) \mid l \longrightarrow r \in T\}$ and $\rho(\lambda) = \lambda$, $\rho(wa) = a \rho(w)$, $a \in \Sigma$, $w \in \Sigma^*$. It is easily seen that this rewriting system is terminating with respect to the syllable ordering with status right induced by the precedence $a_1^{-1} \succ a_1 \succ \ldots \succ a_n^{-1} \succ a_n$. In order to show (local) confluence we will need the following fact:

If $a_1^{i_1} \ldots a_n^{i_n}$ is the normal form of x with respect to T, then $a_n^{i_n} \ldots a_1^{i_1}$ is a normal form of $\rho(x)$ with respect to $\rho(T)$.

This is due to the fact that in case $x \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{(l,r) \in T}\,$ } y$ then there exists a rule $(\rho(l),\rho(r))$ in $\rho(T)$ such that $\rho(x) \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{(\rho(l),\rho(r))}\,$ } \rho(y)$.

Now to see that our system $(\Sigma,\rho(T))$ is confluent we take a closer look at possible critical pairs. Such pairs are due to the following two possible overlaps of rules $(\rho(l_1),\rho(r_1))$ and $(\rho(l_2),\rho(r_2))$: In case we have x,y in $\Sigma^*$ such that $x\rho(l_1) \equiv\rho(l_2)y$ this corresponds to an overlap $l_1\rho(x) \equiv\rho(y)l_2$ respectively if we have $x \rho(l_1)y \equiv\rho(l_2)$ this corresponds to an overlap $\rho(y)l_1\rho(x) \equiv l_2$ of the rules (l₁,r₁) and (l₂,r₂) in T. Now since the critical pairs for T are confluent and the overlaps for $\rho(T)$ are just reversed instances of these systems, we know that they reduce to the same common descendant which is a reverse instance of the common descendant in the T-case. Hence the rewriting system is confluent and obviously it has similar properties as the original system and gives us normal forms of the desired form.