Timeline for Modifying Dehn's algorithm to allow equal length replacements?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 28, 2020 at 15:35 | comment | added | YCor | It should be emphasized that one main advantage of Dehn's algorithm is its efficiency. The example of $\mathbf{Z}^2$ (mentioned by Derek) shows that the modified algorithm can be extremely inefficient: if we start with $x^ny^nx^{-n}y^{-n}$, most algorithm operations preserve the length and if we blindly do them, we probably have to do exponentially many until we get the right ones (those leading to a simplification). | |
| Jan 28, 2020 at 15:29 | comment | added | YCor | A group has a presentation satisfying Dehn's algorithm iff it's Gromov-hyperbolic. So the question eventually is whether there is a non-hyperbolic group with a presentation satisfied the "modified" Dehn algorithm. | |
| Jan 28, 2020 at 15:20 | answer | added | IJL | timeline score: 1 | |
| Feb 25, 2014 at 12:26 | answer | added | HJRW | timeline score: 5 | |
| Feb 24, 2014 at 22:57 | answer | added | Derek Holt | timeline score: 6 | |
| Feb 24, 2014 at 20:17 | comment | added | Andy Putman | Remark : A group $G$ has a presentation for which there is a classical Dehn algorithm if and only if $G$ is hyperbolic. You indicated that you know the "if" direction; for the "only if" direction, it is clear that if there is a presentation where the classical Dehn algorithm works, then the group has a linear Dehn function (which is known to be equivalent to hyperbolicity). | |
| Feb 24, 2014 at 19:36 | comment | added | Gerhard Paseman | I suspect there are no other such group clases known: I imagine one can well-(partial-)order the words and run a variant of Dehn's algorithm using the well-order. There may be issues of definability, and so one can't just use "any" well-order. In particular, I think one can define a group G' and a translation of rules so that length-preserving rules in G become length reducing rules in G', and get essentially the same results. Gerhard "Is Just Guessing About This" Paseman, 2014.02.24 | |
| Feb 24, 2014 at 18:16 | history | asked | Mike Jury | CC BY-SA 3.0 |