Groups that do and do not have context-sensitive word problem

Derek F. Holt, Sarah Rees, Michael Shapiro

We prove that a group has word problem that is a growing context-sensitive language precisely if its word problem can be solved using a non-deterministic Cannon's algorithm (the de…