Invited speakers

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.

Bakhadyr Khoussainov (University of Auckland, New Zealand)

Parity games are almost in P.

Parity games form a class of perfect information two player games. These games emerged as an important class through their connections to model checking, verification, mu-calculus, various logics, automata theory, and Markov chains. Given a parity game with n nodes and d colours the problem consists of finding the winner of the game. Emerson, Jutla, and Sistla showed that the problem is in NP and co-NP. It is an old open problem if the winners of parity games can be found in polynomial time. In this talk, we define parity games, present motivation, give examples, and explain basic ideas of the quasi-polynomial time algorithm that solves the parity games problem. As a corollary we explain why these games are fixed parameter tractable, where the parameter is d the number of colours. The algorithm significantly improves all the previously known algorithms in terms of running time. Although the original problem is still open, this work gives a glimpse of hope towards its positive solution. The talk is based on the paper written jointly with C. Calude, S. Jain, W.Li, and F. Stephan. The paper received best paper award at STOC 2017 held in Montreal.

Alexander Okhotin (Saint Petersburg State University, Russia)

A tale of conjunctive grammars

Conjunctive grammars are an extension of ordinary (“context-free”)
grammars with a conjunction operator, which can be used in any rules to
specify a substring that satisfies several syntactic conditions
simultaneously. This family has been systematically studied since the
turn of the century, and is a subject of current studies. This paper
gives an overview of the current state of the art in the research on
conjunctive grammars.

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.