Oliver Goodman,Michael Shapiro Oliver Goodman

Viewing Dehn's algorithm as a rewriting system, we generalize to allow an alphabet containing letters which do not necessarily represent group elements. This extends the class of groups for which the algorithm solves the word problem to inc...

Derek F Holt,Sarah Rees,Michael Shapiro Derek F Holt

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 ...