32 citations · 184 across the 63 of their papers we have counts for
5 papers · 1 filter
The Post correspondence problem in groups
Alexei Myasnikov, Andrey Nikolaev, Alexander Ushakov
We generalize the classical Post correspondence problem () and its non-homogeneous variation () to non-commutative groups and study the computation…
Groups acting on hyperbolic -metric spaces
Andrei-Paul Grecianu, Alexei Kvaschuk, Alexei Myasnikov +1
In this paper we study group actions on hyperbolic -metric spaces, where is an ordered abelian group. -metric spaces were first introduced by Morgan and Shalen in their s…
Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
Volker Diekert, Alexei Miasnikov, Armin Weiß
The conjugacy problem belongs to algorithmic group theory. It is the following question: given two words x, y over generators of a fixed group G, decide whether x and y are conjuga…
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…
Knapsack Problems in Groups
Alexei Myasnikov, Andrey Nikolaev, Alexander Ushakov
We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well…