Аннотация:
Односторонняя система Туэ - это набор правил подстановок слов, позволяющих переписывать слова в данном алфавите, заменяя одни подслова на другие. Функцией сложности вывода $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$.
|
