Showing math.GRShow all
2 papers · 1 filter
math.GR2008
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…
math.GR2007
On a generalization of Dehn's algorithm
Oliver Goodman, Michael Shapiro
Viewing Dehn's algorithm as a rewriting system, we generalise to allow an alphabet containing letters which do not necessarily represent group elements. This extends the class of g…