Polynomial-time proofs that groups are hyperbolic

Derek Holt, Stephen Linton, Max Neunhoeffer, Richard Parker, Markus Pfeiffer, Colva M. Roney-Dougal

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
18 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)419-475
JournalJournal of Symbolic Computation
Volume104
Early online date14 Aug 2020
DOIs
Publication statusPublished - May 2021

Keywords

  • Hyperbolic groups
  • Word problem
  • van Kampen diagrams
  • Curvature

Fingerprint

Dive into the research topics of 'Polynomial-time proofs that groups are hyperbolic'. Together they form a unique fingerprint.

Cite this