Mini-course "Combinatorics on words". Lecturer: Guilhem Gamard

On November 13-20, 2017 Guilhem Gamard  will give a mini-course "Combinatorics on words".

Address: Faculty of computer science, Kochnovsky proezd, 3.
Language: English
Schedule:
13.11.2017     10:30-13:30 (room 306)
20.11.2017     12:10-15:00 (room 306)

If you have questions, please contact the manager of the laboratory Ekaterina Vavilova: evavilova@hse.ru.
Video of lectures 

Abstract

This minicourse is an introduction to combinatorics on words, where “words” mean “strings of characters”. Of course this relates with text algorithms, but there is much more to see! Words connect with algebra, data compression, error-correcting codes, number theory, image processing… Both theory and practice benefit from them. In order to give you a flavour of how powerful such a simple structure can be, we will survey different aspects of this theory throughout 4 lectures.
In the first lecture, we will cover the basics (definitions, etc.) and explore the interactions with algebra: how to handle strings by doing algebra, and conversely what words can bring to algebraists. We will outline a few applications, from online text editors to image processing.
In the second lecture, we will cover infinite words and try to answer the question: how “complicated” an infinite word can be? Our main tool will be substitutions, which can modelize a wide range of phenomena. We will see how this tool can be use to answer questions about combinatorial games, such as Chess or the towers of Hanoi, or to generate lesser-known (but beautiful) fractals.
In the third lecture, we will cover symbolic dynamics, a technique to simplify dynamical systems. We will reuse all knowledge from lecture 2 to study such systems. The lecture will start with a gentle introduction to dynamical systems theory, so everybody can follow it.
Finally in the fourth lecture, we will cover a much narrower subject: quasiperiodicity. Although quasiperiodicity was motivated by the analysis of DNA and quasicrystal, we will focus on the technical details of results and proofs rather than applications. The idea of this last lecture is to show how current research (2016) on the topic feels like.
The first lecture is self-contained and can be followed alone. The prerequisites are minimal (if you know how to reason by induction, you are fine). In case you are interested but cannot attend, contact me: very detailed lecture notes will be available.