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

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

Monday, June 20

9:30 am team meetings

Tuesday, June 21

9:30 am team meetings
3:00 pm coffee
3:30 pm Guest speaker: Dr. Paul Duvall, UNCG and NSA

The Discrete Logarithm Problem


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

Wednesday, June 22

9:30 am team meetings

Thursday, June 23

9:30 am team meetings

Friday, June 24

9:30 am team meetings
11:30 am lunch at Olive Garden Restaurant
1:00 pm Guest speaker: Ajay Chriscoe, IBM

Local periods and binary partial words: An algorithm


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. Partial words were recently introduced in this context. The motivation behind the notion of a partial word is the comparison of genes (or proteins). Alignment of two genes (or two proteins) can be viewed as a construction of partial words that are said to be compatible.

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 n over a finite alphabet A is a partial function from {1,...,n} into A. Elements of {1,...,n} without an image are called holes. A word is just a partial word without holes. The notion of a period of a word is central in combinatorics on words. In the case of partial words, there are two notions: one is that of period, the other is that of local period.

This paper extends to partial words with one hole the well known result of Guibas and Odlyzko which states that for every word u, there exists a word v of same length as u over the alphabet {0,1} such that the set of all periods of u coincides with the set of all periods of v. Our result states that for every partial word u with one hole, there exists a partial word v of same length as u with at most one hole over the alphabet {0,1} such that the set of all periods of u coincides with the set of all periods of v and the set of all local periods of u coincides with the set of all local periods of v.

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

Saturday, June 25

9:30 am team meetings