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

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

2008-01-29

arxiv.org/abs/0801.4533v1

Mathematics

Group Theory

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Groups that do and do not have context-sensitive word problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Groups that do and do not have context-sensitive word problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Groups that do and do not have context-sensitive word problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-186058