Kombinatorika na slovech

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Požadavky:

Osnova přednášek:

1. Kombinatorika na slovech: přehled pojmů a výsledků.

2. Volný monoid, volná grupa, rovnice na slovech.

3. Míry kombinatorické složitosti – faktorová, palindromická, abelovská, aritmetická komplexita.

4. De Bruijnovy a Rauzyho grafy – návratová slova, derivovaná slova.

5. Palindromický a antipalindromický uzávěr.

6. Sturmovská slova a jejich zobecnění – slova kódující výměnu intervalů, Arnoux-Rauzyho slova.

7. Pevné body morfizmů a jejich vlastnosti.

8. Slova bez výskytu zvolených konfigurací: slova bez překryvu, čtvercuprostá slova.

9. Algoritmy v kombinatorice na slovech.

Osnova cvičení:

Cíle studia:

Studijní materiály:

1.M. Lothaire: Combinatorics on Words, 2nd edition, Cambridge, 1997.

2.P. Fogg: Substitutions in Dynamics, Arithmetics and Combinatorics, Springer, 2002.

3.J. Berstel et al.: Combinatorics on Words, Christoffel Words and Repetitions in Words, CRM Series, AMS, 2009.

4.Combinatorics, Words and Symbolic Dynamics, V. Berthé and M. Rigo, eds., Encyclopedia of Mathematics and its Applications, Cambridge, 2016.

5.Sequences, Groups, and Number Theory, V. Berthé and M. Rigo, eds., Trends in Mathematics, Birhäuser Basel, 2018.

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: