Equations on partial words

Issue		RAIRO-Theor. Inf. Appl. Volume 43, Number 1, January-March 2009


Page(s)		23 - 39
DOI		10.1051/ita:2007041
Published online		20 December 2007

RAIRO-Theor. Inf. Appl. 43, 23-39 (2009)
DOI: 10.1051/ita:2007041

Francine 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 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.
² 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^n \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 2007

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.