TCS oriented refs/survey on group theoretic word problem

Question

The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now strong interconnections between the two are now known.

Are there any TCS-oriented references or surveys on the word problem for groups or its applications?

Related questions:

1. bridge problems for group theory/formal languages, cs.se
2. Uses of algebraic structures in theoretical computer science, tcs.se

Related posts on RJ Lipton's blog:

1. Gromov's Theorem
2. Word problem for free groups

Answer 1

I think that you can start (and probably end, because it's a huge list :-) with the references in the recent Charles F. Miller's paper: "Turing machines to word problems" (2013).

And another recent paper that surveys the connections between group theory and theory of automata and formal languages and hase a huge (>100 entries) reference section is:

Tullio Ceccherini-Silberstein, Michel Coornaert, Francesca Fiorenzi, Paul E. Schupp. Groups, graphs, languages, automata, games and second-order monadic logic. European Journal of Combinatorics, Volume 33, Issue 7, October 2012, Pages 1330-1368.

Abstract: In this paper we survey some surprising connections between group theory, the theory of automata and formal languages, the theory of ends, infinite games of perfect information, and monadic second-order logic.

Answer 2

One family of results not mentioned in the excellent references of @Marzio's answer is relations between the isoperimetric (Dehn) function of a group $G$ and the nondeterministic time complexity of the word problem in $G$. For example:

• For finitely generated groups $G$, $WP(G) \in \mathsf{NP}$ if and only if $G$ can be embedded in a finitely presented group that has polynomial Dehn function. (In fact, if $WP(G)$ can be solved in $\mathsf{NTIME}(T(n))$, then $G$ can be embedded in a group with isoperimetric function $\leq n^2 T(n^2)^4$.) (Birget-Ol'shanskii-Rips-Sapir)

• There are individual groups whose word problem is $\mathsf{NP}$-complete (corollary to the preceding), and similarly groups whose word problem is $\mathsf{coNP}$-complete (Birget, also available on the arXiv).

• The collection of functions $\mathcal{D}_4$ that are Dehn functions $\geq n^4$ of finitely presented groups are closely related to the collection $\mathcal{T}_4$ of time functions $\geq n^4$ of nondeterministic Turing machines. Specifically, $\mathcal{T}^4 \subseteq \mathcal{D}_4 \subseteq \mathcal{T}_4$, where $\mathcal{T}^4$ is the set of super-additive functions that are fourth powers of time functions of nondeterministic TMs. (Sapir-Birget-Rips)

See this survey by Sapir for more.