RAIRO-Theor. Inf. Appl.
Volume 43, Number 1, January-March 2009
|Page(s)||23 - 39|
|Published online||20 December 2007|
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.