Browse All

Theses & Dissertations

Submissions

  • Submissions (Articles, Chapters, and other finished products)

EQUATIONS ON PARTIAL WORDS

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Francine Blanchet-Sadri, Professor (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

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 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. ?

Additional Information

Publication
RAIRO - Theoretical Informatics and Applications
Language: English
Date: 2009
Keywords
Equations on words, equations on partial words, commutativity, conjugacy, free monoid