EQUATIONS ON PARTIAL WORDS
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 Schiitzenberger 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 (up arrow). Among other equations, we solve xy up arrow yx, xz up arrow zy, and special cases of x(m)y(n) up arrow z(p) for integers m, n, p >= 2.
equations on partial words commutativity conjugacy equations on words free monoid