title: GROUPS THAT DO AND DO NOT HAVE GROWING CONTEXT-SENSITIVE WORD PROBLEM.
abstract: 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.
authors.affiliation: Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK.
authors.forename: Derek F
authors.initials: DF
authors.lastname: Holt
authors.forename: Sarah
authors.initials: S
authors.lastname: Rees
authors.forename: Michael
authors.initials: M
authors.lastname: Shapiro