A note on Context Sensitive languages and Word Problems

Details A note on Context Sensitive languages and Word Problems A note on Context Sensitive languages and Word Problems

1993-06-16

arxiv.org/abs/math/9306204v1

Mathematics

Group Theory

AMS-Tex, 3 pages, no figures

Scientific paper

Anisimov and Seifert show that a group has a regular word problem ifand only if it is finite. Muller and Schupp (together with Dunwoody's accessibility result) show that a group has context free word problem if and only if it is virtually free. In this note, we exhibit a class of groups where the word problem is as close as possible to being a context sensitive language. This class includes the automatic groups and is closed under passing to finitely generated subgroups. Consequently, it is quite large, including many groups which are not finitely presented.

Affiliated with

Also associated with

No associations

Rating

A note on Context Sensitive languages and Word Problems 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 A note on Context Sensitive languages and Word Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on Context Sensitive languages and Word Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-485399