City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Inroduction to combinatorics on words
Saint Petersburg / autumn 2011, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

We consider several basic notions of combinatorics on words, either directly related to applied algorithmic problems, or of theoretical interest.

Is there a word on a finite alphabet which does not contain two consecutive equal subwords? How can we estimate the number of words of a given length avoiding factors of a given form? How many factors of a given length can a word have? And what about words appearing in its arithmetic progressions? What theory arises from words coding discretized straight lines?