MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I believe that it was an open question back when I was a graduate student whether every word hyperbolic group admits a finite complete (=Church-Rosser=Noetherian+confluent) rewriting system for some finite generating set.

I am basically wondering if this question is still open, and if not what is the counterexample. (I find it hard to believe that every word hyperbolic group does have a finite complete rewriting system but would be happy also if somebody has proven this.)

The only necessary conditions I know for having a finite complete rewriting system are solvable word problem and $FP_{\infty}$.

share|cite|improve this question
I do not think there is an example. As a candidate, I would take the intermediate groups in the construction of a free Burnside group. – Mark Sapir Jul 15 '13 at 18:49
By the way, every hyperbolic group has a complete rewriting system "at 1", i.e. a finite rewriting system which is terminating and confluent at 1: if $u=1$, and $u\to v, u\to w$, then $v\to 1, w\to 1$. Take all words of length $\le 100\delta$ that are equal to 1. For each such word $w$ include all relations $u\to v$ where $u$ is a subword of $w$, $|u|> 1/2|w|$, $v$ is the complement of $u$ in $w$ (considered as a cyclic word). Derek Holt probably knows examples when that rewriting system is not complete (in general). – Mark Sapir Jul 15 '13 at 18:59
@MarkSapir, is such a rewriting system complete for surface groups? – Benjamin Steinberg Jul 15 '13 at 19:02
For surface groups, there is another complete rewriting system - by Susan Hermiller (see my book). Whether this one is confluent, I do not know, never thought about it. I think Susan or Derek Holt must know. – Mark Sapir Jul 15 '13 at 19:05
@Mark: Your Dehn algorithm example cannot be complete in general, because it is strictly length reducing. In the (silly) example $\langle x,y \mid x=y \rangle$, $x$ and $y$ would be irreducible words representing the same group element. But I don't even know if there is an example of a hyperbolic group with given generating set for which it is known that there is no finite complete rewriting system. There may be examples if we fix the generating set and insist that the rewriting system is length non-increasing. – Derek Holt Jul 15 '13 at 19:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.