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

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






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


О субквадратичных функциях сложности вывода для односторонних систем Туэ

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

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

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

Аннотация: Односторонняя система Туэ — это набор правил подстановок слов $S=\{A_i\to B_i\}$, состоящих в замене слова вида $UA_iV$ на слово вида $UB_iV$. Функцией сложности вывода $f_S(n)$ данной односторонней системы Туэ называется наибольшая длина цепочки преобразований, начинающейся от слова длины $n$.
В 2012 г. Кобаяши доказал, что для почти любой сверхквадратичной функции $g(n)$ можно найти одностороннюю систему Туэ, для которой её функция сложности вывода асимптотически эквивалентна $g(n)$, то есть при всех достаточно больших $n$ выполнено $c_1 g(n) < f_S(n) <c_2 g(n)$ для некоторых чисел $c_1,c_2>0$. В той же работе Кобаяши поставил вопрос, существует ли односторонняя система Туэ, для которой функция сложности вывода эквивалентна функции вида $n^\alpha$ при $1<\alpha<2$. В докладе такая система будет построена для любого рационального числа $\alpha>1$.

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