Good Triple Equation on Partial Words


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:

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.

Valid XHTML 1.1!

Valid CSS!

Visit the NSF home page.

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.