Groups that do and do not have growing context-sensitive wordproblem (2008)

Author(s): Holt DF, Rees SE, Shapiro M

    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.

      • Journal: International Journal of Algebra and Computation
      • Volume: 18
      • Issue: 7
      • Pages: 1179-1191
      • Publisher: World Scientific
      • Publication type: Article
      • Bibliographic status: Published

      Keywords: Cannon\'s algorithm


      Professor Sarah Rees
      Professor of Pure Mathematics