<p>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: "<a href="http://www.ms.unimelb.edu.au/~cfm/papers/paperpdfs/tmtwp-lnl-v41-2013.pdf">Turing machines to word problems</a>" (2013).</p>

<p>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:</p>

<p>Tullio Ceccherini-Silberstein, Michel Coornaert, Francesca Fiorenzi, Paul E. Schupp. <a href="http://arxiv.org/pdf/1201.3108.pdf">Groups, graphs, languages, automata, games and second-order monadic logic.</a> European Journal of Combinatorics, Volume 33, Issue 7, October 2012, Pages 1330-1368.</p>

<p><strong>Abstract:</strong> 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.</p>

CC BY-SA 3.0
2014-04-11T21:27:31.463Z
2014-04-11T22:00:35.060Z
2014-04-11T22:00:35.060Z
Marzio De Biasi
<p>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:</p>

<ul>
<li><p>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$.) (<a href="http://dx.doi.org/10.2307/3597196">Birget-Ol'shanskii-Rips-Sapir</a>)</p></li>
<li><p>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 (<a href="http://dx.doi.org/10.1142/S0218196706002822">Birget</a>, also <a href="http://arxiv.org/abs/math/0310335">available on the arXiv</a>).</p></li>
<li><p>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. (<a href="http://dx.doi.org/10.2307/3597195">Sapir-Birget-Rips</a>)</p></li>
</ul>

<p>See <a href="http://arxiv.org/abs/1012.1325">this survey by Sapir</a> for more.</p>

CC BY-SA 3.0
2014-04-12T03:31:08.620Z
2014-04-12T03:31:08.620Z
Joshua Grochow
<p>The <a href="https://en.wikipedia.org/wiki/Word_problem_for_groups" rel="nofollow noreferrer">word problem for groups</a> 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.</p>

<blockquote>
  <p>Are there any TCS-oriented references or surveys on the word problem for groups or its applications?</p>
</blockquote>

<p>Related questions:</p>

<ol>
<li><a href="https://cs.stackexchange.com/questions/14398/bridge-theorems-for-group-theory-and-formal-languages">bridge problems for group theory/formal languages</a>, cs.se</li>
<li><a href="https://cstheory.stackexchange.com/questions/10916/uses-of-algebraic-structures-in-theoretical-computer-science">Uses of algebraic structures in theoretical computer science</a>, tcs.se</li>
</ol>

<p>Related posts on RJ Lipton's blog:</p>

<ol>
<li><a href="http://rjlipton.wordpress.com/2013/06/20/three-theorems-about-growth/" rel="nofollow noreferrer">Gromov's Theorem</a></li>
<li><a href="http://rjlipton.wordpress.com/2009/04/16/the-word-problem-for-free-groups/" rel="nofollow noreferrer">Word problem for free groups</a></li>
</ol>

CC BY-SA 3.0
2014-04-11T21:27:48.150Z
ok I converted the comment to an answer
Marzio De Biasi
<reference-request><soft-question><big-picture><application-of-theory><gr.group-theory>
TCS oriented refs/survey on group theoretic word problem
vzn
# TCS oriented refs/survey on group theoretic word problem

(Asked by: username_0 on 2014-04-11)

The [word problem for groups](https://en.wikipedia.org/wiki/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](https://cs.stackexchange.com/questions/14398/bridge-theorems-for-group-theory-and-formal-languages), cs.se
2. [Uses of algebraic structures in theoretical computer science](https://cstheory.stackexchange.com/questions/10916/uses-of-algebraic-structures-in-theoretical-computer-science), tcs.se

Related posts on RJ Lipton's blog:

1. [Gromov's Theorem](http://rjlipton.wordpress.com/2013/06/20/three-theorems-about-growth/)
2. [Word problem for free groups](http://rjlipton.wordpress.com/2009/04/16/the-word-problem-for-free-groups/)

**Tags:** reference-request, soft-question, big-picture, application-of-theory, gr.group-theory
> **Comments:**
> **username_1**: ok I converted the comment to an answer  

---

## 2 answers

### Answer by username_1 on 2014-04-11. Score: 7 | Accepted answer

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](http://www.ms.unimelb.edu.au/~cfm/papers/paperpdfs/tmtwp-lnl-v41-2013.pdf)" (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.](http://arxiv.org/pdf/1201.3108.pdf) 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 by username_2 on 2014-04-12. Score: 8

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](http://dx.doi.org/10.2307/3597196))
* 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](http://dx.doi.org/10.1142/S0218196706002822), also [available on the arXiv](http://arxiv.org/abs/math/0310335)).
* 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](http://dx.doi.org/10.2307/3597195))

See [this survey by Sapir](http://arxiv.org/abs/1012.1325) for more.


---

