Completion process and quasi-convex subgroups

We show how to effectively compute a graphical representation for a finitely generated quasi-convex subgroup $H$ of an automatic group $G$ (e.g. a hyperbolic group, a right-angled Artin group etc.). Such representations, which are well-known for subgroups of free groups but also in a number of other situations (e.g. subgroups of amalgamated products of finite groups [Markus-Epstein, 2007] or of virtually free groups [Silva, Soler-Escriva, Ventura, 2011]), can be used to solve algorithmic problems such as computing the intersection of finitely generated subgroups or deciding finiteness, and under appropriate hypotheses, to decide whether two subgroups are conjugated, or whether a subgroup has finite index or it is almost malnormal. We also discuss the complexity of computation of this graphical representation: there is no computable bound on the time required to compute it, given the automatic structure of $G$ and a set of words generating $H$; on the other hand, if we are given the quasi-convexity index $k$ of $H$, then the computation can be performed in time at most exponential in $k$ and the lengths of the generators. Finally we also describe how to construct similar automata for finitely generated relatively quasi-convex subgroups of toral relatively hyperbolic groups and how to solve different algorithmic problems for them.