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

Derek F. Holt, Sarah Rees, Michael Shapiro

Research output: Contribution to journalArticlepeer-review

6 Citations (SciVal)


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 deterministic algorithms being defined by Goodman and Shapiro in [6]). We generalize results of [6] to find many examples of groups not admitting non-deterministic Cannon's algorithms. This adds to the examples of Kambites and Otto in [7] of groups separating context-sensitive and growing context-sensitive word problems, and provides a new language-theoretic separation result.
Original languageEnglish
Pages (from-to)1179-1191
Number of pages13
JournalInternational Journal of Algebra and Computation
Issue number7
Publication statusPublished - 2008


Dive into the research topics of 'Groups that do and do not have context-sensitive word problem'. Together they form a unique fingerprint.

Cite this