# Good Triple Equation on Partial Words

## x2 ↑ ymz

Good Triple

Let x, y, and z be partial words such that z is a proper prefix of y. Then x2 is compatible with ymz, (x2 ymz), for some positive integer m if and only if there exist partial words u, v, u0 , v0 , . . ., um - 1 , vm - 1 , zx such that u ≠ ε, v ≠ ε, y = uv,

x = (u0v0) . . .(un - 1vn - 1)un
= vn
(un + 1vn + 1). . .(um - 1vm - 1)zx

where 0 ≤ n < m, u ui and v vi for all 0 ≤ i < m, z zx , and where one of the following holds:

• m = 2n, |u| < |v| , and there exist partial words u', u'n such that zx = u' un , z = uu'n , u u', and un u'n .
• m = 2n + 1, |u| > |v| , and there exist partial words v'2n and z'x such that un = v2n zx , u = v'2n z'x , v2n v'2n and zx z'x .

A triple of partial words (x, y, z) which satisfy these properties we will refer to as a good triple.

The program takes as input three partial words x, y, z such that z is a proper prefix of y.
The program outputs an integer m such that x2ymz (if such m exists) and shows the decomposition of x, y, and z.

 Acknowledgement:   This material is based upon work supported by the National Science Foundation under Grant No. DMS-0452020. Disclaimer:   Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.