Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \newcommand{\Al}{\mathtt{A}} $

$XY\sa{b}X = \sa{a}Y\sa{b}X\sa{ba}$ with $|X|=3$ and $|Y|=4$ admits a (unique) solution $\psi$ defined by $\psi(X)=\sa{aba}$ and $\psi(Y)=\sa{baba}$:

On the contrary, the equation $\sa{a}XY=Y\sa{b}X$ has no solution, because $\sa{a}\psi(X)$ and $\sa{b}\psi(X)$ must be conjugate, which is incompatible with both $|\sa{a}\psi(X)|_{\sa{a}}=1+|\psi(X)|_{\sa{a}}$ and $|\sa{b}\psi(X)|_{\sa{a}}=|\psi(X)|_{\sa{a}}$, while the equation $\sa{a}XY=Y\sa{a}X=$ has $\Al^{|X|}$ solutions when $|X|=|Y|-1$.

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.

References

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.

125 Problems in Text Algorithms

Example

Problem 119: Word Equations with Given Lengths of Variables

References