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?
- bridge problems for group theory/formal languages, cs.se
- Uses of algebraic structures in theoretical computer science, tcs.se
Related posts on RJ Lipton's blog: