23 citations · 112 across the 42 of their papers we have counts for
3 papers · 2 filters
SLP compression for solutions of equations with constraints in free and hyperbolic groups
Volker Diekert, Olga Kharlampovich, Atefeh Mohajeri Moghaddam
The paper is a part of an ongoing program which aims to show that the existential theory in free groups (hyperbolic groups or even toral relatively hyperbolic) is NP-complete. For…
Quadratic Equations in Hyperbolic Groups are NP-complete
Olga Kharlampovich, Atefeh Mohajeri, Alex Taam +1
We prove that in a torsion-free hyperbolic group , the length of the value of each variable in a minimal solution of a quadratic equation is bounded by for an ori…
Decidability of the Elementary Theory of a Torsion-Free Hyperbolic Group
Olga Kharlampovich, Alexei Myasnikov
Let G be a torsion free hyperbolic group. We prove that the elementary theory of G is decidable and admits an effective quantifier elimination to boolean combination of AE-formulas…