Equations on partial words
Department of Computer Science, University of North Carolina,
P.O. Box 26170, Greensboro, North Carolina 27402–6170, USA; firstname.lastname@example.org
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.
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 xMyN = zP has only periodic solutions in a free monoid, that is, if xMyN = zP 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 special cases of xmyn ↑ zp for integers m,n,p ≥ 2.
Mathematics Subject Classification: 68R15
Key words: Equations on words / equations on partial words / commutativity / conjugacy / free monoid.
© EDP Sciences, 2008