Groups that do and do not have growing context-sensitive wordproblem

Derek F. Holt, Sarah Rees and Michael Shapiro

Keywords

word problem, formal languages, grammars, Dehn algorithm, growing context-sensitive

Status

published in Int. J. Alg. Comput. 18 (2008) 1179-1191.

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 \cite{GoodmanShapiro}). We generalise results of \cite{GoodmanShapiro} to find many examples of groups not admitting non-deterministic Cannon's algorithms. This adds to the examples of Kambites and Otto in~\cite{KambitesOtto} of groups separating context-sensitive and growing context-sensitive word problems, and provides a new language-theoretic separation result. \

The preprint is available as gzipped dvi (28 kB), postscript (140 kB) and pdf files.

Alternatively, you can request a copy by e-mailing me.