Good Pair Equation on Partial Words


Good Pair

Let x, y be partial words and let m, n be positive integers such that xm is compatible with yn, (xmyn), with gcd(m,n) = 1. Assume that for all i H(x) the word

yn^ ( i )yn^ ( i + |x| ). . .yn^ ( i + ( m - 1 )|x| )

is 1-periodic and that for all i H(y) the word

xm^ ( i )xm^ ( i + |y| ). . .xm^ ( i + ( n - 1 )|y| )

is 1-periodic. A pair of partial words (x, y) which satisfies this property we will refer to as a good pair. Then there exists a partial word z such that x is contained in z k, (x z k), and y z l for some integers k, l.

The program takes as input a good pair (x, y) of partial words.
The program outputs a partial word z and integers k,l such that xz k and yz l .

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.