Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары






«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
18 апреля 2017 г. 18:30, г. Москва, ауд. 16-04 ГЗ МГУ
 


О количестве слов данной длины, не содержащих $\alpha$-степеней - I

А. Л. Таламбуца

Математический институт им. В.А. Стеклова Российской академии наук, г. Москва

Количество просмотров:
Эта страница:92

Аннотация: Пусть $X$ — слово в алфавите $\mathcal{A}$, а $\alpha$ – положительное число, тогда слово $Y$ называется $\alpha$-степенью если $Y$ может быть записано в виде $Y=X^rX_1$, где слово $X_1$ есть начало слова $X$, и для длин слов выполнено неравенство $|Y|\geqslant\alpha |X|$. Известно, что для любого $\alpha>2$ в двубуквенном алфавите существует бесконечно много слов, не содержащих $\alpha$-степеней. В докладе будет рассказано о том, что при любом $\alpha>7/3$ существует экспоненциально много двубуквенных слов длины $n$, не содержащих $\alpha$-степени, а при любом $\alpha\leqslant 7/3$ лишь полиномиальное число таких слов.
(Доклад по совместной работе Карумяки и Шаллита 2003 года).

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021