Sequence equations

One can ask whether by replacing variables by sequences one can satisfy so-called word or string equations such as

Flatten[{x, 0, x, 0, y}]  Flatten[{y, x, 0, y, 1, 0, 1, 0, 0}]

(with shortest solution x = {1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0}, y = {1, 0, 1, 0, 0, 1, 0, 1, 0, 0}). Knowing about PCP and Diophantine equations one might expect that in general this would be undecidable. But in 1977 Gennadií Makanin gave a complicated algorithm that solves the problem completely in a finite number of steps (though in general triple exponential in the length of the equation).