The compressed conjugacy problem in relatively hyperbolic groups
The conjugacy problem \(\mathsf{CP}(G)\) for a group \(G\) takes as input two words \(u\), \(v\) over a generating set \(\Sigma\). The problem is solvable if there is an algorithm that can determine for any such input whether \(u\) and \(v\) are conjugate in \(G\). The answer yes or no is returned.NEWLINENEWLINEThe compressed conjugacy problem \(\mathsf{CCP}(G)\) takes as input straight line programs, \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\), which define compressed versions of words \(u\) and \(v\), and asks whether the group elements represented by those values are conjugate in \(G\). In the case when the answer is positive, a solution to the problem would normally be expected to compute a conjugator \(g\), which would be returned as an straight line program for a word representing \(g\). Complexity is measured in terms of the sizes of the input straight line programs, which can be significantly less than the sizes of their values.NEWLINENEWLINEThe main result of the paper under review is Theorem A: The compressed conjugacy problem for a group that is hyperbolic relative to a collection of free abelian subgroups is solvable in polynomial time.
- Finite generating sets of relatively hyperbolic groups and applications to geodesic languages
- scientific article; zbMATH DE number 53661 (Why is no real title available?)
- scientific article; zbMATH DE number 1385418 (Why is no real title available?)
- Relatively hyperbolic groups
- Relatively hyperbolic groups.
- Relatively hyperbolic groups: intrinsic geometry, algebraic properties, and algorithmic problems
- The compressed word problem in relatively hyperbolic groups
- THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
This page was built for publication: The compressed conjugacy problem in relatively hyperbolic groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6495843)
