Given a quasi-convex subgroup $H$ of hyperbolic $G$, can we decide if two elements $x,y \in G$ lie in the same double coset of $H$? I've come across the following question in my research, which seems elusive but is almost surely decidable.
Let $H$ be a quasi-convex subgroup of the hyperbolic group $G$. Given $x, y \in G$, we wish to decide whether $HxH = HyH$. This is equivalent to asking whether there exists $h, h' \in H$ such that $hx = yh'$.
It is easy to see that the question $x \in yH$ is easily decidable, since $H$ has a solvable membership problem and this reduces to checking whether $y^{-1} x \in H$.
The double coset problem seems harder, but the instinct is that this might solved by bounding the lengths of $h, h'$, akin to the solution to the conjugacy problem.
Does this problem appear in the literature anywhere? Any references or thoughts are appreciated.
Thanks!
 A: This is answered for free groups in Membership to double cosets in free groups and the same method basically works for hyperbolic groups.  You might as well do double cosets $HgK$ with $H,K$ both quasiconvex.   Then $w\in HgK$ if and only if $Hw\cap gK$ intersect nontrivially.
Now the set of geodesic words belonging to $Hw$ is a regular language and there are known algorithms for constructing an automaton recognizing these languages (HJRW mentioned this in the comments for subgroups, but it is more or less straightforward to generalize for cosets) and similarly for $gK$.  Therefore the geodesic words in $Hw\cap gK$ are recognized by a finite automaton that you can construct.  Since emptiness is decidable for finite automata, you are done.  You need the quasi-convexity constants of course to build these automata.
I should mention the algorithms for these things I have seen do not appear super-effecitve.  The point is if $H$ is $L$-quasiconvex, then to get the automaton for $Hw$ you construct the $(L+|w|)$-neighborhood of the coset $H$ in the Schreier graph associated to $G/H$ and make $H$ the start state and $Hw$ the final state and intersect with the automaton computing the language of geodesic words for $G$.  Any geodesic for an element of $Hw$ does not leave this $(L+|w|)$-neighborhood by quasi-convexity.  One can build this fragment of the Schreier graph via a Todd-Coxeter style method: see section 4 of https://arxiv.org/pdf/1408.1917.pdf.   However, there are some classes of groups (like surface groups) where more efficient means to build this core are known.
