Groups that do and do not have context-sensitive word problem

Simple item page
dc.creatorHolt, Derek F.
dc.creatorRees, Sarah
dc.creatorShapiro, Michael
dc.date2008-01-29
dc.date.accessioned2026-07-07T08:57:08Z
dc.date.available2026-07-07T08:57:08Z
dc.descriptionWe 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). We generalise their results to find many examples of groups not admitting non-deterministic Cannon's algorithms. This adds to the examples of Kambites and Otto of groups separating context-sensitive and growing context-sensitive word problems, and provides a new language-theoretic separation result.
dc.identifierhttps://arxiv.org/abs/0801.4533
dc.identifierhttp://arxiv.org/abs/0801.4533
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/146853
dc.subjectGroup Theory
dc.subject20F65, 20F10
dc.titleGroups that do and do not have context-sensitive word problem
dc.typetext

Files

Collections

arXiv