Periods, partial words, and an extension of a result of Guibas and Odlyzko
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Brian Shirey (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
- Advisor
- Francine Blanchet-Sadri
Abstract: "A well known and unexpected result of Guibas and Odlyzko states that the set of all periods of a word is independent of the alphabet size (alphabets with one symbol are excluded here). More specifically, for every word u, there exists a word v over the alphabet {0, 1} such that u and v have the same length and the same set of periods. Recently, Blanchet-Sadri and Chriscoe extended this fundamental result to words with one "do not know" symbol also called partial words with one hole. They showed that for every partial word u with one hole, there exists a partial word v with at most one hole over the alphabet {0, 1} such that u and v have the same length, the same set of periods, the same set of weak periods, and H(v) H(u)," where H(u) (respectively, H(v)) denotes the set of holes of u (respectively, v). In this paper, we extend this result further to a large class of partial words. Given a partial word u belonging to that class, our proof provides an algorithm to compute a partial word v over {0, 1} sharing the same length and same sets of periods and weak periods as u, and satisfying H(v) H(u)."--Abstract from author supplied metadata.
Periods, partial words, and an extension of a result of Guibas and Odlyzko
PDF (Portable Document Format)
1543 KB
Created on 5/1/2007
Views: 1392
Additional Information
- Publication
- Thesis
- Language: English
- Date: 2007
- Keywords
- Guibas, Odlyzko, words
- Subjects
- Word problems (Mathematics)
- Mathematics--Data processing.
- Combinatorial analysis