Effective construction of covers of canonical Hom-diagrams for equations over torsion-free hyperbolic groups

Abstract

We show that, given a finitely generated group $G$ as the coordinate group of a finite system of equations over a torsion-free hyperbolic group $\Gamma$, there is an algorithm which constructs a cover of a canonical solution diagram. The diagram encodes all homomorphisms from $G$ to $\Gamma$ as compositions of factorizations through $\Gamma$-NTQ groups and canonical automorphisms of the corresponding NTQ-subgroups. We also give another characterization of $\Gamma$-limit groups as iterated generalized doubles over $\Gamma$.

Corrected according to referee suggestions. Accepted to Groups, Complexity, Cryptology