Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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.

[img]
Preview
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

Request Changes to record.

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:
DateEvent
May 2021Published
14 August 2020Available
6 August 2020Accepted
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:
Project/Grant IDRIOXX Funder NameFunder ID
EP/I03582X/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us