Word equations with two variables

The problem whether the set of all equations that are satisfiable in some free semigroup- or, equivalently, in an algebra of words with concatenation- is recursive (usually called the satisfiability problem for semigroup equations) was first formulated by A.A. Markov in early sixties (see [3]). Special cases of the problem were solved affirmatively by A.A. Markov (see [3]), Yu.I. Khmelevskiı ̆ [8], [7], G. Plotkin, [14] and A. Lentin [11]