Polynomial-time word problems. (Q951964)

The author observes that automorphisms of the free group strongly resemble straight-line programs, which are widely studied in the theory of compressed data structures in computer science. A crucial result by M. Lohrey is used that the word problem for compressed words in the free group is solvable in polynomial time. This theorem is applied to 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 handlebody subgroup of the mapping class group. The paper is self-contained. A detailed exposition of the necessary results from computer science including Plandowski theorem is given.