Избегание паттернов. Паттерн Зимина.

Исполнительное резюме

Тема относится к комбинаторике слов. Исторически она начинается с работ Axel Thue 1906 и 1912 годов о бесквадратных и перекрытие-свободных словах; в современном виде теория избегания паттернов была формализована в 1979 году в статье Avoidable Patterns in Strings of Symbols и независимо в 1982/1984 году в статье A. I. Zimin Blocking Sets of Terms. Центральный факт: паттерн \(p\) с \(n\) различными переменными является неизбежным тогда и только тогда, когда он встречается в \(Z*n\), где \(Z*n\) — \(n\)-й паттерн Зимина. Это превращает \(Z\*n\) в полный тест на неизбежность.

Для решения задач практически важны четыре инструмента. Первый: критерий Зимина, то есть проверка вхождения паттерна в \(Z*n\). Второй: длиновой критерий \( |p|\le 2^n-1 \) для неизбежного паттерна с \(n\) переменными; в частности, любой паттерн длины \(\ge 2^n\) избегаем. Третий: свободные буквы и редукции BEM-типа. Четвёртый: алгоритмический критерий через короткие границы, дающий линейное вычисление Zimin type слова и квадратичный поиск \(Z*k\) в произвольном слове.

Количественная сторона задачи описывается функцией \(f(n,q)\): это минимальная длина, начиная с которой каждое слово над \(q\)-буквенным алфавитом содержит \(Z\*n\). Из точных значений базовые: \(f(1,q)=1\), \(f(2,q)=2q+1\), а также \(f(3,2)=29\). Для фиксированного \(q\) рост \(f(n,q)\) по \(n\) имеет башенный тип; для \(n=3\) известно \(f(3,q)=\Theta(2^q q!)\).

С вычислительной точки зрения общая задача распознавания неизбежности паттерна NP-полна, но отдельные подзадачи существенно проще: проверка свободной буквы полиномиальна, вычисление Zimin type префиксов — линейно, поиск \(Z\*k\) в префиксах слова Фибоначчи — логарифмичен.

Формальный аппарат

Пусть \(\Delta\) — алфавит переменных, \(\Sigma\) — конечный алфавит букв. Паттерн — это непустое слово \(p\in \Delta^+\). Слово \(w\in\Sigma^\*\) встречает паттерн \(p\), если существует не стирающий морфизм \(h:\Delta^\*\to\Sigma^\*\) такой, что \(h(p)\) является фактором слова \(w\). Если такого морфизма нет, \(w\) избегает \(p\). Паттерн называется \(k\)-избегаемым, если существует бесконечное слово над \(k\)-буквенным алфавитом, избегающее \(p\); его индекс избегаемости \(\lambda(p)\) — минимальное такое \(k\), а \(\lambda(p)=\infty\) означает неизбежность. Паттерн называется \(q\)-неизбежным, если любое достаточно длинное \(q\)-ичное слово его встречает; неизбежный означает \(q\)-неизбежный для всех \(q\ge1\).

Рекурсивно определяются паттерны Зимина: [ Z1=x1,\qquad Z{n+1}=Zn\,x{n+1}\,Zn. ] Первые члены: [ Z2=x1x2x1,\qquad Z3=x1x2x1x3x1x2x1,\qquad Z4=x1x2x1x3x1x2x1x4x1x2x1x3x1x2x1. ] После переобозначения \(x*1=a,x*2=b,x*3=c,x*4=d\) получаем [ Z3=abacaba,\qquad Z4=abacabadabacaba. ] Из рекурсии сразу следует \(|Z*n|=2^n-1\), а буква \(x*i\) входит в \(Z\*n\) ровно \(2^{\,n-i}\) раз.

Рекурсивная структура \(Z*n\) удобна в виде дерева вложений. Она не добавляет новых фактов по сравнению с формулой выше, а лишь визуализирует разбиение \(Z*{n+1}=Z*nx\_{n+1}Z*n\).

Для редукционных критериев нужна свободная буква. Буква \(x\) паттерна \(w\) называется свободной, если не существует цепочки 2-факторов вида [ xa_1,\; b_1a_1,\; b_1a_2,\; b_2a_2,\; \dots,\; b_nx, ] где все перечисленные двубуквенные слова являются факторами \(w\). Если \(x\) встречается один раз, то она автоматически свободна. Обозначим через \(w^x\) слово, полученное удалением всех вхождений \(x\). Тогда действует базовая лемма: если \(x\) свободна в \(w\) и \(w^x\) неизбежно, то \(w\) неизбежно. В современной формулировке Sauer/BEM есть и более сильный критерий через последовательности удалений свободных букв и отождествлений букв.

Для алгоритмов над конкретным словом \(u\) вводится Zimin type: [ \mathrm{Ztype}(u)=\max{k:\; u \text{ является образом } Z*k \text{ при не стирающем морфизме}}. ] Для пустого слова \(\mathrm{Ztype}(\varepsilon)=0\). Если \(\mathrm{ShortBord}(u)\) — наибольшая собственная граница длины \(<|u|/2\), то [ \mathrm{Ztype}(u)=1+\mathrm{Ztype}(\mathrm{ShortBord}(u)). ] Это ключевая рекурсия для линейного алгоритма.

Ниже — компактное сравнение основных вариантов задачи.

Основные теоремы и доказательства

Ключевая теорема темы такова: если паттерн \(p\) содержит ровно \(n\) различных переменных, то \(p\) неизбежен тогда и только тогда, когда \(Z\*n\) встречает \(p\). Это и есть стандартная BEM–Zimin-характеризация неизбежности. В одной линии она говорит: все неизбежные паттерны ровно те, которые “сидят внутри” соответствующего паттерна Зимина.

Доказательство направления \(Z\*n \Rightarrow\) неизбежность. Если \(Z*n\) встречает \(p\), то существует не стирающий морфизм \(h\), для которого \(h(p)\) — фактор \(Z*n\). Так как \(Z*n\) неизбежен, то любое достаточно длинное слово \(w\) над любым конечным алфавитом содержит некоторый образ \(g(Z*n)\). Тогда фактор \(g(h(p))\) является в \(w\) вхождением \(p\). Следовательно, \(p\) неизбежен. Обратное направление существенно нетривиально и составляет содержательную часть работ 1979 и 1982/1984 годов; именно там доказывается, что всякий неизбежный паттерн можно обнаружить внутри \(Z\*n\).

Из этой теоремы немедленно вытекает главный длиновой критерий. Пусть \(p\) неизбежен и использует \(n\) переменных. Тогда \(Z*n\) встречает \(p\), то есть существует фактор \(u\) паттерна \(Z*n\), равный \(h(p)\) для не стирающего морфизма \(h\). Поскольку \(h\) не стирает буквы, \(|h(p)|\ge |p|\). Но \(|h(p)|=|u|\le |Z*n|=2^n-1\). Значит, [ |p|\le 2^n-1. ] Следовательно, любой паттерн с \(n\) переменными и длиной \(\ge 2^n\) избегаем. Если же \(|p|=2^n-1\), то все образы переменных должны иметь длину 1 и соответствующий фактор должен совпасть со всем \(Z*n\); значит, \(p\) совпадает с \(Z\*n\) с точностью до переименования переменных. Именно это в отдельной форме доказывается в Long Unavoidable Patterns*.

Практическая lемма о свободной букве такова: если \(x\) свободна в \(\alpha\), а \(\alpha^x\) неизбежно, то \(\alpha\) неизбежно. Она полезна для задач “снизу вверх”: сначала доказывается неизбежность укороченного паттерна, затем обратно добавляется свободная буква. Самый частый частный случай — буква, встречающаяся ровно один раз. Она всегда свободна.

Для \(Z*2=x*1x*2x*1\) есть точный критерий в терминах текста: слово \(w\) содержит \(Z*2\) тогда и только тогда, когда некоторая буква встречается в \(w\) в двух несоседних позициях. Отсюда сразу получается точная формула [ f(2,q)=2q+1. ] Доказательство. Максимальный \(q\)-ичный избегатель \(Z*2\) может содержать каждую букву не более чем в одном блоке длины 1 или 2, иначе найдутся две несоседние одинаковые буквы. Значит, длина любого избегателя не превосходит \(2q\). С другой стороны, слово [ a_1a_1a_2a_2\cdots a_qa_q ] имеет длину \(2q\) и избегает \(Z\*2\), поскольку каждой букве соответствуют только соседние вхождения. Следовательно, порог равен \(2q+1\).

Для бинарных паттернов известны два важных критерия. Во-первых, в статье Every Binary Pattern of Length Six is Avoidable on the Two-Letter Alphabet доказано, что всякий паттерн на двух переменных длины не менее 6 является 2-избегаемым; граница точна, потому что существуют 2-неизбегаемые паттерны длины 5. Во-вторых, Unavoidable Binary Patterns даёт полную классификацию неизбежных бинарных паттернов. Для задач это означает: при двух переменных уже одна длина несёт очень много информации.

С количественной стороны важна функция [ f(n,q)=\min{M:\; \text{любое } q\text{-ичное слово длины } M \text{ содержит } Z*n}. ] Для неё известны базовые точные значения и сильные асимптотики: \(f(1,q)=1\), \(f(2,q)=2q+1\), \(f(3,2)=29\), \(f(3,q)=\Theta(2^q q!)\), а при фиксированном \(q\) рост по \(n\) имеет башенный тип. В 2019 году были получены по существу точные верхние и нижние оценки этого типа.

Алгоритмы и вычислительные методы

Алгоритмически полезно разделять три задачи: проверка свободной буквы в паттерне, проверка общей неизбежности паттерна и поиск \(Z\*k\) в конкретном слове. Их вычислительная сложность существенно различается.

Псевдокод линейного вычисления Zimin type повторяет опубликованный алгоритм Rytter–Shur.

Algorithm ComputeZiminTypes(x[1..m])
 B[0]:= -1
 B[1]:= 0
 Z[0]:= 0
 Z[1]:= 1
 t:= 0
 s:= 0

 for i:= 2 to m do
 while t >= 0 and x[t+1] != x[i] do
 t:= B[t]
 t:= t + 1
 B[i]:= t

 while s >= 0 and (2*s + 1 >= i or x[s+1] != x[i]) do
 s:= B[s]
 s:= s + 1

 Z[i]:= Z[s] + 1

 return Z

Корректность опирается на формулу через \(\mathrm{ShortBord}\), а линейность — на тот же амортизационный анализ, что и у Morris–Pratt: каждая неудачная переустановка указателя компенсируется будущим продвижением вправо.

Для распознавания общей неизбежности естественен недетерминированный перебор по редукциям BEM-типа. В худшем случае он экспоненциален; это согласуется с NP-полнотой задачи.

Algorithm IsUnavoidable(alpha)
 normalize variable names in alpha
 if alpha has 1 symbol total then
 return True

 for each free letter x in alpha do
 if IsUnavoidable(delete_all(alpha, x)) then
 return True

 for each unordered pair of distinct letters x, y in alpha do
 beta:= identify(alpha, x -> y)
 if IsUnavoidable(beta) then
 return True

 return False

Такой алгоритм полезен как учебный и для малых входов. Для строгой оценки: каждая ветвь использует только полиномиальные подшаги (в частности, проверку свободной буквы), но число ветвей растёт combinatorially; в общей постановке задача NP-полна.

Для ручного решения задач удобно следовать короткому маршруту: сначала считать число переменных \(n\), затем применять длиновой критерий \(2^n-1\); если он не решает задачу, искать свободые одиночные буквы; затем пробовать явное вхождение в \(Z\*n\); для слов — использовать короткие границы и Zimin type.

Типовые задачи с решениями

Ниже восемь задач возрастающей сложности. Они покрывают основные техники: рекурсию \(Z\*n\), длиновой критерий, свободые буквы, граф свободности, Zimin type и количественные оценки.

Задача 1. Выписать \(Z*1,Z*2,Z*3,Z*4\). Найти \(|Z*n|\) и число вхождений каждой переменной \(x*i\) в \(Z\*n\).

Решение. По определению [ Z1=x1,\qquad Z{n+1}=Znx{n+1}Zn. ] Следовательно, [ Z2=x1x2x1,\quad Z3=x1x2x1x3x1x2x1,\quad Z4=x1x2x1x3x1x2x1x4x1x2x1x3x1x2x1. ] Для длины имеем рекурсию \(L*{n+1}=2L_n+1\), \(L_1=1\), откуда \(L_n=2^n-1\). Для кратности буквы \(x*i\): при переходе \(Z*n\to Z*{n+1}\) все старые буквы удваиваются, а новая \(x*{n+1}\) входит ровно один раз. Поэтому \(\\#*{x*i}(Z*n)=2^{n-i}\).

Задача 2. Доказать: если паттерн \(p\) с \(n\) различными переменными неизбежен, то \(|p|\le 2^n-1\). Применить это к паттерну \(abab\).

Решение. По теореме Зимина неизбежный \(p\) встречается в \(Z*n\). Значит, имеется не стирающий морфизм \(h\) такой, что \(h(p)\) — фактор \(Z*n\). Тогда \(|p|\le |h(p)|\le |Z\*n|=2^n-1\). Для \(p=abab\): число переменных равно \(2\), а \(|abab|=4>2^2-1=3\). Следовательно, \(abab\) избегаем.

Задача 3. Показать, что паттерн \(abca\) неизбежен.

Решение. Буква \(b\) встречается ровно один раз, значит, она свободна. После удаления \(b\) получаем паттерн \(aca\), который совпадает с \(Z*2\) с точностью до переименования переменных. Паттерн \(Z*2\) неизбежен. По лемме о свободной букве из неизбежности \(aca\) следует неизбежность \(abca\). Альтернативно: \(abca\) явно встречается в \(Z*3=abacaba\), если положить \(a\mapsto x*1\), \(b\mapsto x*2x*1\), \(c\mapsto x*3\); тогда образ \(abca\) равен \(x*1x*2x*1x*3x*1\), а это фактор \(Z\*3\).

Задача 4. Определить, свободна ли буква \(b\) в паттерне \(abcbab\). Затем решить, неизбежен ли этот паттерн.

Решение. Его 2-факторы: \(ab,bc,cb,ba\). Для проверки свободности \(b\) по графу 2-факторов стартовыми являются вершины \(0ba,0bc\), а целевыми — \(1ab,1cb\). Достижимость:

• \(0bc\to 1bc\to 0bc,0ba\);
• \(0ba\to 1ba\to 0bc,0ba\).

Ни \(1ab\), ни \(1cb\) недостижимы, значит, \(b\) свободна. После удаления \(b\) получаем \(aca\cong Z\*2\), а значит, по лемме о свободной букве \(abcbab\) неизбежен.

Задача 5. Найти \(f(2,4)\).

Решение. Для \(Z*2\) действует точная формула \(f(2,q)=2q+1\). Поэтому [ f(2,4)=2\cdot 4+1=9. ] Экстремальный избегатель длины \(8\) — \(aabbccdd\): каждая буква повторяется только в соседних позициях, двух несоседних одинаковых букв нет, следовательно, \(Z*2\) не встречается. Любое 4-ичное слово длины \(9\) уже содержит \(Z\*2\).

Задача 6. Вычислить Zimin type всех префиксов слова \(u=\texttt{abacaba}\).

Решение. Используем формулу \(\mathrm{Ztype}(u)=1+\mathrm{Ztype}(\mathrm{ShortBord}(u))\).

Следовательно, \(\texttt{abacaba}\) имеет Zimin type \(3\), то есть является образом \(Z*3\). В самом деле, здесь даже тождественный образ после переименования \(x*1=a,x*2=b,x*3=c\).

Задача 7. Доказать: если \(u\) является образом \(Z*n\), то для любого непустого слова \(v\) слово \(uvu\) является образом \(Z*{n+1}\). Применить к \(u=\texttt{abacaba}\), \(v=\texttt{d}\).

Решение. Пусть \(u=h(Z*n)\). Определим новый морфизм \(h'\) так: [ h'(xi)=h(xi)\quad (1\le i\le n),\qquad h'(x{n+1})=v. ] Тогда [ h'(Z)=h'(ZnxZn)=h(Zn)\,v\,h(Z*n)=uvu. ] Значит, \(uvu\) — образ \(Z*{n+1}\). Для \(u=\texttt{abacaba}\cong Z*3\) и \(v=\texttt{d}\) получаем \(\texttt{abacabadabacaba}\), то есть образ \(Z\*4\).

Задача 8. Получить верхнюю оценку на \(f(3,2)\) из рекуррентной оценки через число минимальных слов типа 2.

Решение. Из Rytter–Shur: [ f(n+1,k)\le (f(n,k)+1)\,m(n,k)+f(n,k), ] где \(m(n,k)\) — число минимальных \(k\)-ичных слов Zimin type \(n\). Для \(n=2,k=2\) в статье вычислено \(m(2,2)=6\), а \(f(2,2)=5\). Поэтому [ f(3,2)\le (5+1)\cdot 6 +5 = 41. ] Это не точное значение, а только верхняя оценка. Точное значение, найденное там же прямым перебором минимальных слов, равно [ f(3,2)=29. ] Такой расчёт важен методически: сначала строится общая оценка, потом она уточняется специализированным перебором.

Источники, история и открытые вопросы

Историческая траектория такова. Работы Туе 1906 и 1912 годов положили начало систематическому изучению повторов и избегаемых структур в словах. Статья 1979 года Avoidable Patterns in Strings of Symbols впервые дала полную характеристику неизбежных паттернов в современном смысле. Русский первоисточник Зимина 1982 года Blocking Sets of Terms дал независимую эквивалентную характеризацию и ввёл центральные объекты, теперь называемые паттернами Зимина. Дальнейшая линия шла в двух направлениях: классификация малых классов паттернов и количественно-алгоритмическое изучение функции \(f(n,q)\) и распознавания.

Ниже — приоритетный список источников, достаточный для учебной и задачной работы.

Открытые и недоисследованные направления в найденных источниках формулируются так. Для полной \(q\)-неизбежности хорошо понятен случай “для всех \(q\)” благодаря критерию Зимина, но уже вопрос о существовании паттернов, которые \(q\)-неизбежны, но \((q+1)\)-избегаемы, существенно труднее; в работе 2017/2019 годов отмечено, что примеры известны для \(q=2,3,4\), а дальнейшее продвижение представляет самостоятельный интерес. Точные значения \(f(n,q)\) известны только в немногих малых случаях; даже следующий после \(f(3,2)\) слой в основном описывается оценками. Для doubled patterns в 2021/2023 годах сформулирована и частично проверена гипотеза: каждый square-free doubled pattern 2-избегаем; доказательство дано лишь до 4 переменных. Наконец, после доказательства NP-полноты общей задачи особенно актуальны структурные подзадачи: какие естественные подклассы паттернов допускают эффективное точное распознавание.