Алексей Леонидович Таламбуца

1 марта 2019

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