Оглавление

1. Словесный моноид. Лемма о коммутирующих словах.
2. Избегание экспонент. Избегание экспоненты 2+ над алфавитом размера 2.
3. Избегание экспонент. Избегание экспоненты 2 над алфавитом размера 3.
4. Избегание экспонент. Теорема Дежан (без доказательства).
5. Избегание паттернов. Паттерн Зимина.
6. Периодические слова. Теорема Файна-Вильфа.
7. Комбинаторная сложность. Теорема о сложности периодических (с предпериодом) слов.
8. Комбинаторная сложность. Слова Штурма. Лемма о сбалансированном множестве и палиндроме.
9. Комбинаторная сложность. Слова Штурма. Теорема об эквивалентности двух определений слов Штурма.
10. Слова Линдона. Лемма о конкатенации слов Линдона.
11. Слова Линдона. Декомпозиция Линдона: существование и единственность.
12. Слова Линдона. Декомпозиция Линдона: алгоритм нахождения декомпозиции Линдона за O(n).
13. Автоматные последовательности. Пример Туэ–Морса.
14. Автоматные последовательности. Теорема Кобхэма.
15. Вероятностный метод. Локальная лемма Ловаса и существование бесквадратных слов.