## Equations on partial words

^{1}
Department of Computer Science, University of North Carolina,
P.O. Box 26170, Greensboro, North Carolina 27402–6170, USA; blanchet@uncg.edu
A research assignment from the University of North Carolina at Greensboro is
gratefully acknowledged. Some of this assignment was spent at the LIAFA: Laboratoire d'Informatique Algorithmique: Fondements et Applications of Université Paris 7, Paris, France, and at the University of Debrecen, Debrecen, Hungary.

^{2}
Department of Mathematics, Texas A&M University, College Station, TX 77843–3368, USA.

^{3}
Department of Mathematics, Tennessee Tech University, Box 5054, Cookeville, TN 38505–0001, USA.

Received:
8
August
2006

Accepted:
23
October
2007

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*holds with integers

^{M}y^{N}= z^{P}*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 special cases of

*x*for integers

^{m}y^{n}↑ z^{p}*m,n,p ≥ 2*.

Mathematics Subject Classification: 68R15

Key words: Equations on words / equations on partial words / commutativity / conjugacy / free monoid.

*© EDP Sciences, 2008*