Equations on partial words

Blanchet-Sadri, Francine ; Blair, D. Dakota ; Lewis, Rebeca V.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 1, pp. 23-39.

Résumé

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\ge 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}^n\uparrow z^p$ for integers $m,n,p\ge 2$.

Détail

DOI : 10.1051/ita:2007041

Classification : 68R15
Mots-clés : equations on words, equations on partial words, commutativity, conjugacy, free monoid