|
|
«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
25 апреля 2017 г. 18:30, г. Москва, Математический институт им.В.А.Стеклова РАН
|
|
|
|
|
|
О количестве слов данной длины, не содержащих $\alpha$-степеней - II
А. Л. Таламбуца Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
|
Количество просмотров: |
Эта страница: | 172 |
|
Аннотация:
В продолжении предыдущего доклада будет доказана вторая часть теоремы
Карумяки–Шаллита о точной границе между полиномиальным и экспоненциальным
ростом количества апериодических слов в двухбуквенном алфавите.
Будет доказано, что мощность множества, состоящего из двубуквенных слов длины $n$,
не содержащих $\alpha$-степени, при $\alpha>7/3$ растёт экспоненциально по $n$.
В предыдущем докладе было доказано, что при $\alpha\leqslant 7/3$ мощность
этого множества растёт полиномиально по $n$.
|
|