Mini-course "Combinatorics on words". Lecture 2 (Guilhem Gamard)

680 views · Published 14 November 2017 · 1:18:32 · Indexed 14 November 2026

Channel: ФКН НИУ ВШЭ · 2017 · Education

Watch on YouTube

This mini-course is an introduction to combinatorics on words, where “words” mean “strings of characters”. Of course, this relates to 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 four lectures.

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 model a wide range of phenomena. We will see how this tool can be used to answer questions about combinatorial games, such as Chess or the towers of Hanoi, or to generate lesser-known (but beautiful) fractals.

Lecturer: Guilhem Gamard, Université Aix-Marseille.

Faculty of Computer Science: https://cs.hse.ru/en/
Follow us: https://www.facebook.com/hsefcs; https://twitter.com/CS_HSE

More from this channel