The Library
Polynomial-time word problems
Tools
Schleimer, Saul (2008) Polynomial-time word problems. Commentarii Mathematici Helvetici, Vol.83 (No.4). pp. 741-765. doi:10.4171/CMH/142 ISSN 0010-2571.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.4171/CMH/142
Abstract
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Commentarii Mathematici Helvetici | ||||
Publisher: | European Mathematical Society Publishing House | ||||
ISSN: | 0010-2571 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.83 | ||||
Number: | No.4 | ||||
Page Range: | pp. 741-765 | ||||
DOI: | 10.4171/CMH/142 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |