×

Computation in word-hyperbolic groups. (English) Zbl 1024.20039

Summary: We describe two practical algorithms for computing with word-hyperbolic groups, both of which we have implemented. The first is a method for estimating the maximum width, if it exists, of geodesic bigons in the Cayley graph of a finitely presented group \(G\). Our procedure will terminate if and only this maximum width exists, and it has been proved by Papasoglu that this is the case if and only if \(G\) is word-hyperbolic. So the algorithm amounts to a method of verifying the property of word-hyperbolicity of \(G\). The aim of the second algorithm is to compute the thinness constant for geodesic triangles in the Cayley graph of \(G\). This seems to be a much more difficult problem, but our implementation does succeed with straightforward examples. Both algorithms involve substantial computations with finite state automata.

MSC:

20F67 Hyperbolic groups and nonpositively curved groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20-04 Software, source code, etc. for problems pertaining to group theory
68W30 Symbolic computation and algebraic computation

References:

[1] DOI: 10.1007/BF01884301 · Zbl 0834.20040 · doi:10.1007/BF01884301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.