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. (2020) Polynomial-time proofs that groups are hyperbolic. Journal of Symbolic Computation . doi:10.1016/j.jsc.2020.08.003 (In Press)
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-polynomial-time-proofs-groups-hyperbolic-Holt.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only until 14 February 2022. Contact author directly, specifying your specific needs. - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1190Kb) |
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 > 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: | 14 August 2020 | ||||||
| Dates: |
|
||||||
| Date of first compliant deposit: | 10 September 2020 | ||||||
| DOI: | 10.1016/j.jsc.2020.08.003 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | In Press | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
