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 xy ↑ yx,
xz ↑ zy, and x m y n ↑ z
p for integers
m, n, p ≥ 2.
