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. ?
EQUATIONS ON PARTIAL WORDS
PDF (Portable Document Format)
697 KB
Created on 6/22/2011
Views: 995
Additional Information
- Publication
- RAIRO - Theoretical Informatics and Applications
- Language: English
- Date: 2009
- Keywords
- Equations on words, equations on partial words, commutativity, conjugacy, free monoid