Skip to content

Research at St Andrews

Polynomial-time proofs that groups are hyperbolic

Research output: Contribution to journalArticlepeer-review

Open Access Status

  • Embargoed (until 14/02/22)

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.
Close

Details

Original languageEnglish
Pages (from-to)419-475
JournalJournal of Symbolic Computation
Volume104
Early online date14 Aug 2020
DOIs
Publication statusE-pub ahead of print - 14 Aug 2020

    Research areas

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

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. GAP package Small Cancellation Theory

    Neunhoeffer, M., Roney-Dougal, C. M., Burdges, J. P., Linton, S. A. & Parker, R. A., 2013, (In preparation)

    Research output: Non-textual formSoftware

  2. Algorithmic Generalisations of Small Cancellation Theory

    Neunhoeffer, M., Roney-Dougal, C. M., Linton, S. A., Parker, R. & Burdges, J. P., 2013, (In preparation) In: Not yet known.

    Research output: Contribution to journalArticlepeer-review

  3. GAP package recog: a GAP package that implements a methods for constructive recognition

    Neunhoeffer, M., Seress, A., Brooksbank, P., Celler, F., Howe, S., Law, M., Linton, S., Malle, G., Niemeyer, A., O'Brien, E. & Roney-Dougal, C., 2009

    Research output: Non-textual formSoftware

  4. Groupoids and Conditional Symmetry

    Gent, I. P., Kelsey, T. W., Linton, S. A., Pearson, J., Roney-Dougal, C. M. & Bessiere, C., Sep 2007, p. 823-830.

    Research output: Contribution to conferencePaperpeer-review

  5. Symmetry and consistency

    Gent, I. P., Kelsey, T., Linton, S. & Roney-Dougal, C., 2005, Principles and Practice of Constraint Programming - CP 2005: Proceedings of the 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005. van Beek, P. (ed.). Springer-Verlag, p. 271-285 15 p. (Lecture Notes in Computer Science; vol. 3709).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related by journal

  1. Lifting tropical bitangents

    Len, Y. & Markwig, H., Jan 2020, In: Journal of Symbolic Computation. 96, p. 122-152

    Research output: Contribution to journalArticlepeer-review

  2. Computing finite semigroups

    East, J., Egri-Nagy, A., Mitchell, J. D. & Péresse, Y., May 2019, In: Journal of Symbolic Computation. 92, p. 110-155 46 p.

    Research output: Contribution to journalArticlepeer-review

  3. New refiners for permutation group search

    Jefferson, C., Pfeiffer, M. & Waldecker, R., May 2019, In: Journal of Symbolic Computation. 92, p. 70-92 23 p.

    Research output: Contribution to journalArticlepeer-review

  4. Integrality and arithmeticity of solvable linear groups

    Detinko, A., Flannery, D. & de Graaf, W., 2015, In: Journal of Symbolic Computation. 68, p. 138–145

    Research output: Contribution to journalArticlepeer-review

ID: 269496332

Top