Abstract of Paper

On the Length of the Minimum Solution of Word Equations in One Variable
by Kensuke Baba, Satoshi Tsuruta, Ayumi Shinohara, and Masayuki Takeda

Abstract:

We show the {\em tight upperbound} of the length of the minimum solution 
of a word equation $L=R$ in one variable, in terms of the differences 
between the positions of corresponding variable occurrences in $L$ and $R$. 
By introducing the notion of difference, the proof is obtained from 
Fine and Wilf's theorem. As a corollary, it implies that the length of 
the minimum solution is less than $N=\vert L\vert+\vert R\vert$.