Good Triple Equation on Partial Words

Let x, y, and z be partial words such that z is a proper prefix of y. Then x² is compatible with y^mz, (x² ↑ y^mz), for some positive integer m if and only if there exist partial words u, v, u₀ , v₀ , . . ., u_{m - 1} , v_{m - 1} , z_x such that u ≠ ε, v ≠ ε, y = uv,

x = (u₀v₀) . . .(u_{n - 1}v_{n - 1})u_n
                  = v_n(u_{n + 1}v_{n + 1}). . .(u_{m - 1}v_{m - 1})z_x

where 0 ≤ n < m, u ↑ u_i and v ↑ v_i for all 0 ≤ i < m, z ↑ z_x , and where one of the following holds:

• m = 2n, |u| < |v| , and there exist partial words u', u'_n such that z_x = u' u_n , z = uu'_n , u ↑ u', and u_n ↑ u'_n .
• m = 2n + 1, |u| > |v| , and there exist partial words v'_2n and z'_x such that u_n = v_2n z_x , u = v'_2n z'_x , v_2n ↑ v'_2n and z_x ↑ z'_x .

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