I would like to know of any examples of families of groups that are known (or conjectured) to have a solvable uniform word problem, i.e. an algorithm that given a presentation $P$ of a group in the family, and a word $W$ in the generators of $P$, decides whether $W$ represents the identity of the group defined by $P$.


In particular, I'm curious about finitely generated Fuchsian groups.



Examples of group families with solvable uniform word problem
Derek Holt is the expert here - I hope he will correct me where I err.




---


There are many such families. Here are a few ones that spring to mind (or were mentioned in the comments above), in no particular order.


1. fuchsian groups
2. fundamental groups of three-manifolds
3. hyperbolic groups
4. automatic groups
5. one-relator groups
6. residually finite groups




---


Here is the general idea for families (1) to (5). Suppose that $\mathcal{F}$ is a family of (finitely presentable) groups. Suppose also that $\mathcal{F}$ comes with a solution to the "certification problem". That is, there is an algorithm that, given a finite presentation $P$ of a group $G \in \mathcal{F}$, produces a (useful!) proof that $G$ lies in $\mathcal{F}$. We then use this proof to solve the word problem for $P$.




---


Here is an example in more detail. Suppose that $\mathcal{F\_3}$ is the family of fundamental groups of closed, connected three-manifolds. Given a presentation $P$ (promised to be of a group in $\mathcal{F\_3}$), our algorithm returns


1. a one-vertex triangulation $T$ of a three-manifold $M$ and
2. a sequence of Tietze moves connecting $P$ to the triangulated presentation of $\pi\_1(M)$ coming from $T$.


The existence of an algorithm for the word problem for $\pi\_1(M)$ (and thus $P$) follows from geometrisation.




---


Another example may be integer linear groups, but there is a subtle point. We need an algorithm that, given a finite collection of invertible integer matrices, produces a finite presentation of the group they generate. Does such an algorithm exist?


**EDIT:** As pointed out by HJRW (in the comments) there is no such algorithm. This is [proven](https://arxiv.org/abs/1003.5117v2) by Bridson and Wilton.


