Polynomial-time word problems

Details Polynomial-time word problems Polynomial-time word problems

2006-08-23

arxiv.org/abs/math/0608563v1

Mathematics

Group Theory

25 pages, 6 figures

Scientific paper

We find polynomial-time solutions to the word problem for free-by-cyclic groups, the word problem for automorphism groups of free groups, and the membership problem for the handlebody subgroup of the mapping class group. All of these results follow from observing that automorphisms of the free group strongly resemble straight line programs, which are widely studied in the theory of compressed data structures. In an effort to be self-contained we give a detailed exposition of the necessary results from computer science.

Affiliated with

Also associated with

No associations

Rating

Polynomial-time 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 Polynomial-time word problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial-time word problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-110125