Question

Consider the braid group $B_n$ presented in terms of the usual Artin generators $\sigma_1,\ldots,\sigma_{n-1}$. Now add the additional relations $\sigma_i^k = 1$ for $i=1,\ldots,n-1$. For lack of a better name, I'll call the resulting group $B_n^{(k)}$. $B_n^{(2)}$ is just the symmetric group $S_n$. As discussed in this mathoverflow thread, $B_n^{(k)}$ is infinite unless $\frac{1}{n}+\frac{1}{k} > \frac{1}{2}$. $B_n$ is an automatic group and thus any word $w$ in the Artin generators can be reduced to a normal form that depends only on the group element in $O(|w|^2)$ time. My question is, for fixed $k > 2$, can one reduce a word $w$ in the generators of $B_n^{(k)}$ to a normal form in $\mathrm{poly}(n,|w|)$ time, too? (It appears to me that direct simpleminded adaptation of the algorithm for braid group normal form fails.)

Answer 1

The groups you are considering are a special class of Shephard groups, which are obtained from Artin groups by adding relators $\sigma_i^{k_i}=1$, $0\le k_i<\infty$ for every Artin generator. Biautomaticity of some of all these groups is conjectured in http://arxiv.org/abs/0901.0094 and this conjecture is verified in some cases. Unfortunately for you, the results in this paper require that the Artin graph contains no triangles with label 2, which will exclude quotients of classical braid groups. Nevertheless, you may want to read the paper to see if the methods could be useful in the context of your question.

Answer 2

Correction: The original answer was incorrect, since non-uniform complex hyperbolic lattices are not automatic

There are analogous groups where this does not hold. Thurston has examples of quotients of mapping class groups of the punctured sphere which are non-uniform complex hyperbolic orbifolds (I think with up to 12 punctures) where the braid generators have finite order. These groups are not automatic, since they are the fundamental groups of non-uniform complex hyperbolic lattices by a result of Farb. I'm not sure to what extent his examples generalize though.