Polynomial-time word problems

Simple item page
dc.creatorSchleimer, Saul
dc.date2006-08-23
dc.date.accessioned2026-07-07T07:22:03Z
dc.date.available2026-07-07T07:22:03Z
dc.descriptionWe 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.
dc.description25 pages, 6 figures
dc.identifierhttps://arxiv.org/abs/math/0608563
dc.identifierhttp://arxiv.org/abs/math/0608563
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/115522
dc.subjectGroup Theory
dc.subjectGeometric Topology
dc.subject20F10; 20F38; 57M07
dc.titlePolynomial-time word problems
dc.typetext

Files

Collections

arXiv