- Tomohiro I (Kyushu Institute of Technology, Japan)
- Bakhadyr Khoussainov (University of Auckland, New Zealand)
- Alexander Okhotin (Saint Petersburg State University, Russia)
- Dominique Perrin (LIGM, Université Paris-Est, France)
- Marinella Sciortino (Universita degli Studi di Palermo, Italy)
- Andrew Winslow (University of Texas, Rio Grande Valley, USA)
Tomohiro I (Kyushu Institute of Technology, Japan)
The Runs Theorem and Beyond
Repetitions in a string are fundamental properties the string possesses, which have been extensively studied in word comtinatorics and utilized in many efficient string processing algorithms. Particularly maximal repetitions, also known as runs, are useful for representing all the repetitions in the string. Since it was shown that the number of runs in a string of length n is upper bounded by O(n) [R. M. Kolpakov and G. Kucherov, Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 1999, pp. 596–604], the following conjecture (known as the “runs” conjecture) have been attracting researchers: The number of runs in a string of length n is upper bounded by n. This conjecture was recently solved affirmatively using a characterization based on Lyndon words. The characterization not only gives a surprisingly simple proof to the 15-years open problem but also provides completely new insights on how repetitions are packed into a string. In this talk I will review the proof and some related topics.
Alexander Okhotin (Saint Petersburg State University, Russia)
Andrew Winslow (University of Texas, Rio Grande Valley, USA)
Algorithmic Aspects of Tiling
Interlocking shapes that disjointly cover or _tile_ the plane have been explored artistically throughout history, for instance on the patterned walls and ceilings of Alhambra, kimono patterns in Japan, and the surreal art of M.C. Escher. They have also been studied in mathematics and physics for more than a hundred years and underlie many of the self-organizing behaviors seen in the natural world. Despite these varied appearances, most algorithmic questions related to tilings remain unanswered. In this talk, we trace the history of these questions chronologically, beginning with Hilbert’s faulty assumption of his 18th of 23 famous problems, and ending with new efficient algorithms for finding some tilings of some shapes.