The Library
Polynomial-time proofs that groups are hyperbolic
Tools
Tools
Tools
Holt, Derek F., Linton, Stephen, Neunhöffer, Max, Parker, Richard, Pfeiffer, Markus and Roney-Dougal, Colva M. (2021) Polynomial-time proofs that groups are hyperbolic. Journal of Symbolic Computation, 104 . pp. 419-475. doi:10.1016/j.jsc.2020.08.003 ISSN 0747-7171.
|
PDF
WRAP-polynomial-time-proofs-groups-hyperbolic-Holt.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1190Kb) | Preview |
Official URL: https://doi.org/10.1016/j.jsc.2020.08.003
Abstract
It is undecidable in general whether a given finitely presented group is word hyperbolic. We use the concept of pregroups, introduced by Stallings (1971), to define a new class of van Kampen diagrams, which represent groups as quotients of virtually free groups. We then present a polynomial-time procedure that analyses these diagrams, and either returns an explicit linear Dehn function for the presentation, or returns fail, together with its reasons for failure. Furthermore, if our procedure succeeds we are often able to produce in polynomial time a word problem solver for the presentation that runs in linear time. Our algorithms have been implemented, and when successful they are many orders of magnitude faster than KBMAG, the only comparable publicly available software.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| Library of Congress Subject Headings (LCSH): | Hyperbolic groups, Curvature, Group theory | ||||||||
| Journal or Publication Title: | Journal of Symbolic Computation | ||||||||
| Publisher: | Academic Press | ||||||||
| ISSN: | 0747-7171 | ||||||||
| Official Date: | May 2021 | ||||||||
| Dates: |
|
||||||||
| Volume: | 104 | ||||||||
| Page Range: | pp. 419-475 | ||||||||
| DOI: | 10.1016/j.jsc.2020.08.003 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 10 September 2020 | ||||||||
| Date of first compliant Open Access: | 14 February 2022 | ||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
