2 citations · 3 across the 9 of their papers we have counts for
14 papers
The halting problem is decidable on a set of asymptotic probability one
Joel David Hamkins, Alexei Miasnikov
The halting problem for Turing machines is decidable on a set of asymptotic probability one. Specifically, there is a set B of Turing machine programs such that (i) B has asymptoti…
Effective JSJ Decompositions
Olga Kharlampovich, Alexei Myasnikov
In this paper we describe an elimination process which is a deterministic rewriting procedure that on each elementary step transforms one system of equations over free groups into…
Implicit function theorem over free groups
O. Kharlampovich, A. Miasnikov
We introduce the notion of a regular quadratic equation and a regular NTQ system over a free group. We prove the results that can be described as Implicit function theorems for alg…
Balanced presentations of the trivial group on two generators and the Andrews-Curtis conjecture
Alexei D. Miasnikov, Alexei G. Myasnikov
The Andrews-Curtis conjecture states that every balanced presentation of the trivial group can be reduced to the standard one by a sequence of the elementary Nielsen transformation…
Whitehead method and Genetic Algorithms
Alexei D. Miasnikov, Alexei G. Myasnikov
In this paper we discuss a genetic version (GWA) of the Whitehead's algorithm, which is one of the basic algorithms in combinatorial group theory. It turns out that GWA is surprisi…
On the Andrews-Curtis equivalence
Alexei D. Myasnikov, Alexei G. Myasnikov, Vladimir Shpilrain
The Andrews-Curtis conjecture claims that every balanced presentation of the trivial group can be reduced to the standard one by a sequence of ``elementary transformations" which a…