RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

RAIRO-Theor. Inf. Appl. (2008)
DOI: 10.1051/ita:2007041

Equations on partial words

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

¹ Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, North Carolina 27402-6170, USA; blanchet@uncg.edu
² Department of Mathematics, Texas A&M University, College Station, TX 77843-3368, USA.
³ Department of Mathematics, Tennessee Tech University, Box 5054, Cookeville, TN 38505-0001, USA.

(Received August 8, 2006. Accepted October 23, 2007. Published online 20 December 2007.)

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ⁿ = z^p has only periodic solutions in a free monoid, that is, if x^m yⁿ = z^p holds with integers m, n, p $\geq$ 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 ( $\uparrow$ ). Among other equations, we solve xy $\uparrow$ yx, xz $\uparrow$ zy, and special cases of x^m yⁿ $\uparrow$ z^p for integers m, n, p $\geq$ 2.

Mathematics Subject Classification. 68R15

Key words: Equations on words -- equations on partial words -- commutativity -- conjugacy -- free monoid

© EDP Sciences 2008