**Algorithmic Combinatorics on Words REU
June 20 - June 26, 2005 (Week 3) Schedule**

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

9:30 am | team meetings |

9:30 am | team meetings |

3:00 pm | coffee |

3:30 pm |
Guest speaker: Dr. Paul Duvall,
UNCG and NSA
The discrete logarithm problem is the basis for the security of a number of cryptographic systems, including the celebrated Diffee-Hellman protocol and the El Gamal system. In this talk, we will describe the problem and some applications, and discuss why it is believed to be difficult. |

5:00 pm | dinner at Liberty Oak Restaurant |

9:30 am | team meetings |

9:30 am | team meetings |

9:30 am | team meetings |

11:30 am | lunch at Olive Garden Restaurant |

1:00 pm |
Guest speaker: Ajay Chriscoe, IBM
The study of the combinatorial properties of strings of symbols from a finite alphabet (also referred
to as words) is profoundly connected to numerous fields such as biology, computer science, mathematics, and physics.
Research in combinatorics on words goes back roughly a century. There is a renewed interest in combinatorics on words
as a result of emerging new application areas such as molecular biology.
While a word can be described by a total function, a partial word can be described by a partial function.
More precisely, a partial word of length
This paper extends to partial words with one hole the well known result of Guibas and Odlyzko which states that for
every word To prove our result, we use the technique of Halava, Harju and Ilie, which they used to characterize constructively the set of periods of a given word. As a consequence of our constructive proof, we obtain a linear time algorithm which, given a partial word with one hole, computes a partial word with at most one hole over the alphabet {0,1} with the same length and the same sets of periods and local periods. A World Wide Web server interface at http://www.uncg.edu/mat/AlgBin/ has been established for automated use of the program. |

9:30 am | team meetings |