On the Length of the Minimum Solution of Word Equations in One Variable.
Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings,
Lecture Notes in Computer Science Vol.2747, pp.189-197
(2003), [peer-reviewed]
Event Date:
August 25-29, 2003
Abstract / 概要
We show the 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…