12
$\begingroup$

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}$.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Commented Jul 15, 2013 at 18:49
  • 1
    $\begingroup$ 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). $\endgroup$
    – user6976
    Commented Jul 15, 2013 at 18:59
  • $\begingroup$ @MarkSapir, is such a rewriting system complete for surface groups? $\endgroup$
    – Benjamin Steinberg
    Commented Jul 15, 2013 at 19:02
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Commented Jul 15, 2013 at 19:05
  • 2
    $\begingroup$ @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. $\endgroup$
    – Derek Holt
    Commented Jul 15, 2013 at 19:29

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .