Elements of finite order for finite monadic Church-Rosser Thue systems

Abstract:

A Thue system $T$ over $\Sigma$ is said to allow nontrivial elements of finite order, if there exist a word $u \in {\Sigma ^ \ast }$ and integers $n \ge 0$ and $k \ge 1$ such that $u \nleftrightarrow _T^ \ast \lambda$ and ${u^{n + k}} \leftrightarrow _T^ \ast {u^n}$. Here the following decision problem is shown to be decidable: Instance. A finite, monadic, Church-Rosser Thue system $T$ over $\Sigma$. Question. Does $T$ allow nontrivial elements of finite order? By a result of Muller and Schupp this implies in particular that given a finite monadic Church-Rosser Thue system $T$ it is decidable whether the monoid presented by $T$ is a free group or not.