Commutativity Equation on Partial Words

xy ↑ yx

Commutativity

Let x and y be non-empty partial words such that |x| ≤ |y| .

If the partial word xy is compatible with the partial word yx, (xy ↑ yx), and xy is not (|x|, |y|)-special, then there exists a word z such that x is contained in z k, (x⊂ zk), and y ⊂ z l for some integers k and l.

The program takes as input a set {x, y} of two partial words such that |x| ≤ |y|, xy ↑ yx, and xy is not (|x|, |y|)-special.
The program outputs a partial word z and integers k, l such that x ⊂ z k and y ⊂ z 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.