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

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






Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
18 июня 2018 г. 18:30–20:05, г. Москва, МИАН (ул. Губкина, 8), ауд. 530 + Zoom
 


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

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

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

Аннотация: Односторонняя система Туэ - это набор правил подстановок слов, позволяющих переписывать слова в данном алфавите, заменяя одни подслова на другие. Функцией сложности вывода $f(n)$ для данной системы называется наибольшая длина цепочки преобразований, начинающейся от слова длины $n$. В работе Ю. Кобаяши 2012 года было доказано, что для почти любой сверхквадратичной функции $g(n)$ можно найти одностороннюю систему Туэ, функция сложности вывода которой $f(n)$ эквивалентна $g(n)$, (то есть $A g(n) < f(n) <B g(n)$ при некоторых $A,B>0$ и достаточно больших $n$). В работе Кобаяши был поставлен вопрос, существуют ли односторонние системы Туэ, для которых функция сложности вывода эквивалентна $n^c$, где $1<c<2$. В докладе будет рассказано о том как строить примеры таких систем для любого рационального числа $c>1$.

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