Commutativity Equation on Partial Words

xyyx

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|, xyyx, and xy is not (|x|, |y|)-special.
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.