Algorithmic Combinatorics on Words REU
June 22 - June 28, 2006 (Week 4) Schedule

All events are in room 335, Bryan Building, unless otherwise noted.

Thursday, June 22

9:00 am team meetings

Friday, June 23

9:00 am team meetings
11:30 am lunch
1:30 pm Guest speaker: Brian Shirey

Periods, Partial Words, and a Result of Guibas and Odlyzko


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 has been established for automated use of the program.

Saturday, June 24

9:00 am team meetings

Monday, June 26

9:00 am team meetings

Tuesday, June 27

9:00 am team meetings

Wednesday, June 28

9:00 am - 10:00 am initial student presentations - Deepak and Gautam
10:15 am - 11:15 am initial student presentations - Tim and Taktin
11:15 am - 1:00 pm break
1:00 pm - 2:00 pm initial student presentations - Naomi and Justin
2:10 pm - 3:10 pm initial student presentations - Crystal and Mihai
3:20 pm - 4:20 pm initial student presentations - Kevin and Josh