1:30 pm |
Guest speaker: Brian Shirey
Periods, Partial Words, and a Result of Guibas and Odlyzko
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, and the same set of weak periods.
In this talk, we (Blanchet-Sadri and Shirey) extend this result further to all
partial words. Given such a partial word u,
our proof provides an algorithm to compute
a partial word v over {0,1}
sharing the same length and the same
sets of periods and weak periods as u.
A World Wide Web server interface at
http://www.uncg.edu/mat/bintwo/
has been established for automated use of the program.
|