Equations on Partial Words

F. Blanchet-Sadri, D. Dakota Blair, and Rebeca V. Lewis

Abstract

It is well known that some of the most basic properties of words, like the commutativity (xy = yx) and the conjugacy (xz = zy), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation x m y n = z p has only periodic solutions in a free monoid, that is, if x m y n = z p holds with integers m, n, p ≥ 2, then there exists a word w such that x, y, z are powers of w. This result, which received a lot of attention, was first proved by Lyndon and Schützenberger for free groups.

In this paper, we investigate equations on partial words. Partial words are sequences over a finite alphabet that may contain a number of “do not know” symbols. When we speak about equations on partial words, we replace the notion of equality (=) with compatibility (↑). Among other equations, we solve xyyx, xzzy, and x m y nz p for integers m, n, p ≥ 2.

Keywords: Equations on words, equations on partial words, commutativity, conjugacy, free monoid.


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.

Visit the Partial Words home page.