- 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)
Marinella Sciortino (Universita degli Studi di Palermo, Italy)
Block sorting-based transformations on words: beyond the magic BWT
The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression and later results have contributed to make it a fundamental tool for the design of self-indexing compressed data structures. Despite its simplicity, the BWT presents some combinatorial properties that have aroused great interest both from the theoretical and applicative points of view. Over the years, many variants of the original BWT have been proposed, but without maintaining all the mathematical properties that make BWT such a versatile tool. Instead, the Alternating Burrows-Wheeler Transform (ABWT) is a recent transformation, studied in the field of Combinatorics on Words, that works similarly to BWT, using an alternating lexicographical order in place of the usual one. Here we show that ABWT, although it is a combinatorial tool with very peculiar properties, can be considered a good candidate to replace the BWT in several contexts. Furthermore, we consider a more general class of block sorting-based transformations on words that prove to be interesting combinatorial tools that offer new research perspectives. Within such a class, BWT and ABWT play a special role.
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.