CLR cover

Problem 119: Word Equations with Given Lengths of Variables

A word equation is an equation between words whose letters are constants or variables. Constants belong to the alphabet $\Al=\{\sa{a},\sa{b},\dots\}$ and variables belong to the disjoint alphabet of unknowns $\mathtt{U}=\{X,Y,\dots\}$. An equation is written $L=R$, where $L,R\in(\Al\cup\mathtt{U})^*$ and a solution of it is a morphism $\psi: (\Al\cup\mathtt{U})^*\rightarrow\Al^*$ leaving constant invariant and for which the equality $\psi(L)=\psi(R)$ holds.

In the problem we assume that the length $|\psi(X)|$ is given for each variable $X$ occurring in the equation and is denoted by $|X|$.

Given a word equation with the variable lengths, show how to check in linear time with respect to the equation length plus the output length if a solution exists.


  • M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002.
  • G. S. Makanin. The problem of solvability of equations in a free semigroup. Math. Sb., 103(2):147-236, 1977. In Russian. English translation in: Math. USSR-Sb, 32, 129-198, 1977.