Invited speakers

and more…


Tomohiro I (Kyushu Institute of Technology, Japan)

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)

Alexander Okhotin (Saint Petersburg State University, Russia)

TBA

 
 
 
 
TBA


Andrew Winslow (University of Texas, Rio Grande Valley, USA)

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.