Словесный моноид. Лемма о коммутирующих словах.

Краткое исполнительное резюме

В пособии фиксируются стандартные определения теории слов в свободном моноиде \(A^\*\) над конечным ненулевым алфавитом \(A\): слова, длина, префиксы/суффиксы, факторы, степени, сопряжённость (циклическая), периоды, примитивные слова и примитивные корни.

Ключевой результат — лемма о коммутирующих словах (часто формулируемая как «первый» результат Роджер Линдон—Марсель-Поль Шютценберже): для \(u,v\in A^+\) равенство \(uv=vu\) эквивалентно существованию слова \(z\in A^+\) и показателей \(k,\ell\in\mathbb N\) таких, что \(u=z^k\), \(v=z^\ell\). Приводятся строгие доказательства и набор эквивалентных формулировок (через примитивный корень, через равенство степеней, через циклический подмоноид).

В блоке периодичности даётся классическая теорема Файна—Уилфа (в форме для конечных слов/строк): если слово длины \(n\) имеет периоды \(p\) и \(q\) и \(n\ge p+q-\gcd(p,q)\), то \(\gcd(p,q)\) тоже является периодом. Излагается оригинальная формулировка Натан Файн—Герберт Уилф для периодических последовательностей и выводится версия для слов.

Показана связь с понятием границы (border) слова и с теоретическими объектами, лежащими в основе алгоритма Дональд Кнут—Джеймс Моррис—Вон Пратт: границы эквивалентны «периодическим корням» (в смысле кратчайшей порождающей периодичности префикса), а массив границ — стандартная структура, используемая в КМП.

Отдельно приводятся следствия: единственность примитивного корня, описание централизатора примитивного слова, а также связанные уравнения слов (включая «второй» результат Линдона—Шютценберже и периодичность-форсирующее уравнение \(a^mb^n=c^k\)).

Базовые определения и нотации

Пусть \(A\) — конечный непустой алфавит. Слово над \(A\) — конечная последовательность букв из \(A\). Множество всех конечных слов (включая пустое) обозначается \(A^\*\). Операция — конкатенация (приписывание), нейтральный элемент — пустое слово \(\varepsilon\) (в ряде источников \(\lambda\) или \(\Lambda\)); тогда \((A^\*,\cdot,\varepsilon)\) — свободный моноид над \(A\).

Длина слова \(w\) — число букв в нём, обозначается \(|w|\), причём \(|\varepsilon|=0\). Для слова \(w=a_1a_2\cdots a_n\) (где \(a_i\in A\)) фиксируем индексацию \(w[i]=a_i\) для \(1\le i\le n\).

Префикс, суффикс, фактор. Для \(u,w\in A^\*\):

• \(u\) — фактор (подслово) \(w\), если \(\exists x,y\in A^\*: w=xuy\).
• \(u\) — префикс \(w\), если \(\exists y\in A^\*: w=uy\).
• \(u\) — суффикс \(w\), если \(\exists x\in A^\*: w=xu\). Фактор/префикс/суффикс называется строгим, если \(u\ne w\).

Степени и степенная запись. Для \(u\in A^\*\) определяем [ u^0=\varepsilon,\qquad u^{n+1}=u^n u\quad (n\in\mathbb N). ] Обозначения \(u^\*=\{u^n:n\ge 0\}\) и \(u^+=\{u^n:n\ge 1\}\).

Сопряжённость (conjugacy) конечных слов. Слова \(u,v\in A^\*\) называются сопряжёнными (циклически сопряжёнными), если \(\exists p,q\in A^\*\) такие, что [ u=pq,\qquad v=qp. ] Эквивалентная (часто используемая) формулировка: \(\exists w\in A^\*\) такое, что \(uw=wv\).

Периоды. Пусть \(w=a*1\cdots a_n\in A^+\). Число \(p\in\{1,\dots,n\}\) называется периодом \(w\), если [ a_i=a*{i+p}\quad \text{для всех } i=1,\dots,n-p. ] Минимальный (по величине) период, если нужен, обозначают \(p(w)\).

Примитивное слово. Непустое слово \(v\in A^+\) называется примитивным, если не существует \(w\in A^+\) и \(n\ge 2\) таких, что \(v=w^n\). Эквивалентно: из \(v=z^n\) следует \(n=1\).

Корни и примитивный корень. Слово \(r\in A^+\) называется корнем слова \(u\in A^+\), если \(\exists k\ge 1\) такое, что \(u=r^k\). Примитивный корень (primitive root) — примитивное \(f\in A^+\) такое, что \(u=f^k\) для некоторого \(k\ge 1\); он единственен. В ряде источников используется обозначение \(\sqrt{u}=f\).

Граница (border) слова \(w\in A^\*\) — слово \(u\in A^\*\) (возможно пустое), такое что \(u\ne w\) и \(u\) является одновременно префиксом и суффиксом \(w\); максимальная граница — граница максимальной длины. В работах о массивах границ подчёркивается комплементарность понятий «граница» и «периодический корень» (кратчайшее слово \(\pi(w)\), по повторению которого \(w\) является префиксом).

Лемма о коммутирующих словах и доказательства

Свойство сокращения в \(A^\*\)

Лемма (левое и правое сокращение). Для любых \(x,y,z\in A^\*\) из \(xy=xz\) следует \(y=z\); из \(yx=zx\) следует \(y=z\).

Доказательство. Рассматривая слова как конечные последовательности букв, равенство \(xy=xz\) означает, что первые \(|x|\) букв слова \(xy\) совпадают с первыми \(|x|\) букв слова \(xz\) и образуют одну и ту же последовательность \(x\); после удаления этих первых \(|x|\) букв остаются \(y\) и \(z\), которые должны совпасть помимо. Аналогично справа. ∎

(Смысл леммы стандартен для свободного моноида слов; используется далее как аксиоматически очевидное свойство равенства последовательностей.)

Основная лемма о коммутировании

Теорема (лемма о коммутирующих словах; «первый» результат Линдона—Шютценберже). Для \(u,v\in A^\*\) выполнено [ uv=vu \quad\Longleftrightarrow\quad \exists\, z\in A^*,\ \exists\, k,\ell\in\mathbb N:\ u=z^k,\ v=z^\ell. ] Если дополнительно \(u,v\in A^+\), то можно требовать \(z\in A^+\) и \(k,\ell\ge 1\).

Доказательство \((\Rightarrow)\) строгой версии для \(u,v\in A^+\)

Пусть \(u,v\in A^+\) и \(uv=vu\). Докажем по индукции по \(N=|u|+|v|\), что \(\exists z\in A^+\) и \(k,\ell\ge 1\) такие, что \(u=z^k\), \(v=z^\ell\).

База. \(N=2\) возможно только при \(|u|=|v|=1\). Тогда \(u\) и \(v\) — буквы, и \(uv=vu\) в свободном моноиде возможно лишь при \(u=v\); берём \(z=u\), \(k=\ell=1\).

Переход. Предположим утверждение верно для всех пар \((u',v')\in (A^+)^2\) с \(|u'|+|v'|<N\). Рассмотрим \(u,v\) с \(|u|+|v|=N\). Без ограничения общности \(|u|\ge |v|\).

Рассмотрим первые \(|v|\) букв слов \(uv\) и \(vu\). В слове \(vu\) это точно \(v\). Так как \(uv=vu\), первые \(|v|\) букв слова \(uv\) тоже равны \(v\). Но первые \(|v|\) букв \(uv\) совпадают с первыми \(|v|\) букв \(u\) (поскольку \(|u|\ge |v|\)). Следовательно, \(v\) — префикс слова \(u\), то есть [ u = v u_1 \quad\text{для некоторого }u_1\in A^*. ] Причём \(u_1\ne \varepsilon\) возможно, но \(|u_1|=|u|-|v|<|u|\), а также \(u_1\in A^\*\) (возможно пустое).

Подставляя \(u=vu_1\) в \(uv=vu\), получаем: [ (vu_1)v = v(vu_1)\quad\Longleftrightarrow\quad v u_1 v = v v u_1. ] Сокращая слева на \(v\) (лемма о сокращении), имеем [ u_1 v = v u_1. ] Если \(u_1=\varepsilon\), то \(u=v\), и можно взять \(z=u\), \(k=\ell=1\). Если \(u_1\in A^+\), то \(|u_1|+|v| < |u|+|v|=N\), и по индукционному предположению существуют \(z\in A^+\) и \(k',\ell'\ge 1\) такие, что \(u_1=z^{k'}\), \(v=z^{\ell'}\). Тогда [ u = v u_1 = z^{\ell'} z^{k'} = z^{\ell'+k'}. ] Полагая \(k=\ell'+k'\), \(\ell=\ell'\), заключаем \(u=z^k\), \(v=z^\ell\). ∎

Доказательство \((\Leftarrow)\)

Если \(u=z^k\) и \(v=z^\ell\), то [ uv=z^{k+\ell}=vu. ] ∎

Эквивалентные формулировки и критерии коммутирования

Ниже перечислены стандартные эквивалентности (все корректны для \(u,v\in A^+\)):

Теорема (критерии коммутирования). Для \(u,v\in A^+\) следующие условия эквивалентны: (i) \(uv=vu\). (ii) \(\exists z\in A^+:\ u,v\in z^\*\) (то есть \(u=z^k,\ v=z^\ell\) для некоторых \(k,\ell\ge 1\)). (iii) \(\sqrt{u}=\sqrt{v}\) (равенство примитивных корней). (iv) \(\exists i,j\ge 1:\ u^i=v^j\).

Доказательство. (i)\(\Leftrightarrow\)(ii) — это теорема о коммутирующих словах выше. (ii)\(\Rightarrow\)(iii): если \(u=z^k\), \(v=z^\ell\), то примитивные корни \(u\) и \(v\) совпадают с примитивным корнем \(z\) (см. лемму об уникальности примитивного корня ниже). (iii)\(\Rightarrow\)(iv): если \(u=(\sqrt u)^k\), \(v=(\sqrt u)^\ell\), то \(u^\ell=v^k\). (iv)\(\Rightarrow\)(ii): из \(u^i=v^j\) следует \(u^i v = v u^i\), то есть \(u^i\) и \(v\) коммутируют; применяя лемму о коммутирующих словах к \((u^i,v)\), получаем \(u^i=w^a\), \(v=w^b\). Далее и \(u\), и \(v\) имеют один и тот же примитивный корень (поскольку \(u\) — корень \(u^i\)), и значит оба лежат в \(z^\*\) для \(z=\sqrt u\). ∎

Примитивный корень: существование и единственность

Лемма (существование и единственность примитивного корня). Для любого \(u\in A^+\) существуют единственные примитивное слово \(f\in A^+\) и число \(k\ge 1\) такие, что \(u=f^k\).

Доказательство. Существование. Если \(u\) примитивно, берём \(f=u\), \(k=1\). Если нет, то \(u=w*1^{k_1}\) для некоторого \(w*1\in A^+\) и \(k_1\ge 2\). Если \(w\*1\) не примитивно, продолжаем процесс. Длины строго убывают, значит процесс конечен и приводит к примитивному \(f\) с \(u=f^k\). *Единственность. Пусть \(u=f^k=g^\ell\), где \(f,g\) примитивны. Тогда \(f^k=g^\ell\Rightarrow f^k g = g f^k\), и по лемме о коммутирующих словах \(f\) и \(g\) — степени одного слова. Так как они примитивны, это возможно лишь при \(f=g\), а тогда и показатель \(k\) определяется однозначно из \(|u|=k|f|\). ∎

Централизатор слова

Следствие (централизатор примитивного слова). Пусть \(p\in A^+\) — примитивное. Тогда множество слов, коммутирующих с \(p\), равно \(p^\*\): [ {x\in A^*: xp=px}=p^*. ] В частности, если \(x\in A^+\) и \(xp=px\), то \(x=p^m\) для некоторого \(m\ge 1\).

Доказательство. Из \(xp=px\) по лемме о коммутирующих словах \(\exists z\in A^+\): \(x=z^k\), \(p=z^\ell\). Примитивность \(p\) даёт \(\ell=1\), то есть \(p=z\), откуда \(x\in p^\*\). Обратное включение очевидно. ∎

Версия «второго» результата Линдона—Шютценберже

Следующий факт часто применяется при анализе перекрытий/границ и тождества \(xy=yz\).

Теорема (второй результат Линдона—Шютценберже). Для \(x,y,z\in A^\*\) выполнено [ xy=yz \quad\Longleftrightarrow\quad \exists e\in\mathbb N\setminus{0},\ \exists u\in A^+,\ \exists v\in A^*:\ x=uv,\ z=vu,\ y=x^e u = u z^e. ]

Эта формулировка даёт нормальную форму всех решений уравнения \(xy=yz\) и, в частности, выводит периодичность множества решений (они порождаются степенями одного «базового» блока).

Сравнение формулировок

Периодичность и связанные теоремы

Теорема Файна—Уилфа в оригинальной форме и версия для слов

Оригинальная статья Натан Файн и Герберт Уилф (1965) формулирует дискретный случай (последовательности) так: две периодические последовательности с периодами \(h\) и \(k\), совпадающие на \(h+k-\gcd(h,k)\) подряд идущих значениях, совпадают всюду; константа оптимальна.

Теорема (Fine–Wilf, дискретный случай). Пусть \((f*n)*{n\ge 0}\) и \((g*n)*{n\ge 0}\) — периодические последовательности (над произвольным множеством значений) периодов \(h\) и \(k\) соответственно. Если [ f_n=g_n\quad \text{для } h+k-\gcd(h,k)\ \text{последовательных }n, ] то \(f_n=g_n\) для всех \(n\ge 0\). Граница \(h+k-\gcd(h,k)\) на длину совпадения неулучшаема.

Доказательство (в стиле статьи Fine–Wilf: идея через производящие функции, дискретный случай). В статье доказывается: если первые \(h+k-\gcd(h,k)\) коэффициентов разности \(H(x)=F(x)-G(x)\) равны нулю, где \(F(x)=\sum*{n\ge 0} f_n x^n\), \(G(x)=\sum*{n\ge 0} g_n x^n\), то при учёте периодичности \(F\) и \(G\) разность \(H\) выражается через множители \((1-x^h)^{-1}\), \((1-x^k)^{-1}\) и \((1-x^{\gcd(h,k)})\) так, что получается многочлен \(R(x)\) малой степени; зануление начальных коэффициентов даёт \(R\equiv 0\) и, следовательно, \(F=G\) и \(f_n=g_n\) для всех \(n\). ∎

Из этой формы выводится классическая «теорема о периодах» для конечных слов.

Определение (период слова). Пусть \(w=a*1\cdots a_n\in A^+\). Число \(p\in\{1,\dots,n\}\) — период \(w\), если \(a_i=a*{i+p}\) для \(1\le i\le n-p\).

Теорема (Fine–Wilf, версия для слов). Пусть \(w\in A^+\) имеет периоды \(p\) и \(q\). Если [ |w|\ \ge\ p+q-\gcd(p,q), ] то \(\gcd(p,q)\) тоже является периодом \(w\).

Доказательство. Пусть \(n=|w|\). Определим две бесконечные периодические последовательности \(f,g:\mathbb N\to A\) так: [ f(i)=w\bigl( ((i-1)\bmod p)+1 \bigr),\qquad g(i)=w\bigl( ((i-1)\bmod q)+1 \bigr). ] Тогда \(f\) имеет период \(p\), а \(g\) имеет период \(q\) по определению. Используя то, что \(p\) — период \(w\), проверяем по индукции по \(i\le n\), что \(f(i)=w[i]\); аналогично \(g(i)=w[i]\). Следовательно, \(f(i)=g(i)\) для всех \(1\le i\le n\). Если \(n\ge p+q-\gcd(p,q)\), то условия теоремы Fine–Wilf (дискретный случай) применимы, и получаем \(f(i)=g(i)\) для всех \(i\ge 1\).

Теперь любая последовательность, имеющая периоды \(p\) и \(q\), имеет также период \(\gcd(p,q)\) (это следует из линейной комбинации периодов и тождества Безу; стандартный факт для бесконечных последовательностей). Тогда \(f\) имеет период \(d=\gcd(p,q)\), т.е. \(f(i)=f(i+d)\) для всех \(i\). Ограничивая это равенство на \(1\le i\le n-d\) и подставляя \(f(i)=w[i]\), получаем \(w[i]=w[i+d]\) для \(1\le i\le n-d\), то есть \(d\) — период \(w\). ∎

Эквивалентная «словесная» формулировка Fine–Wilf через \(u^\omega\)

Для \(u\in A^+\) обозначим \(u^\omega=uuu\cdots\) (бесконечное слово, полученное бесконечным повторением \(u\)). Тогда стандартна эквивалентная форма: \(u\) и \(v\) — степени общего слова тогда и только тогда, когда \(u^\omega\) и \(v^\omega\) имеют общий префикс длины \(|u|+|v|-\gcd(|u|,|v|)\).

Граница слова и связь с периодами

Определение (граница). Слово \(u\) — граница слова \(w\), если \(u\ne w\) и \(u\) одновременно префикс и суффикс \(w\).

Лемма (граница \(\Leftrightarrow\) период). Пусть \(w\in A^+\), \(|w|=n\). Тогда \(w\) имеет период \(p\) тогда и только тогда, когда у \(w\) есть граница длины \(n-p\).

Доказательство. (\(\Rightarrow\)) Если \(p\) — период, то для \(i=1,\dots,n-p\) имеем \(w[i]=w[i+p]\). Это означает, что префикс длины \(n-p\) совпадает с фактором \(w[p+1..n]\), который есть суффикс длины \(n-p\). (\(\Leftarrow\)) Если префикс длины \(n-p\) совпадает с суффиксом длины \(n-p\), то для \(i=1,\dots,n-p\) позиция \(i\) в префиксе совпадает с позицией \(i+p\) в суффиксе, т.е. \(w[i]=w[i+p]\). ∎

Наблюдение о комплементарности границ и «периодических корней» (в смысле кратчайшего слова \(\pi(w)\), порождающего периодическое продолжение, в котором \(w\) — префикс) является стандартным в теории массивов границ и связывается с использованием границ в КМП.

Примитивность и «свойство синхронизации»

Предложение. Если \(u\in A^+\) примитивно, то \(u\) не может быть внутренним фактором слова \(uu\), то есть не существует \(x,y\in A^+\) таких, что \(uu=xuy\).

Доказательство (классическое). Если \(u\) — внутренний фактор \(uu\), то существует разложение \(u=xy=yx\) с \(x,y\in A^+\). Далее по индукции по \(|xy|\) выводится, что \(x\) и \(y\) — степени одного слова, откуда \(u\) не примитивно. ∎

Следствия леммы, критерии и эквивалентные формулировки

Практически используемые следствия

Следствие (описание общего делителя в смысле подмоноида). Если \(u,v\in A^+\) коммутируют, то циклические подмоноиды \(u^\*\) и \(v^\*\) содержатся в одном и том же циклическом подмоноиде \(z^\*\), где \(z\) можно выбирать примитивным (а именно \(z=\sqrt u=\sqrt v\)).

Следствие (равенство степеней). Если \(u^i=v^j\) для некоторых \(u,v\in A^+\) и \(i,j\ge 1\), то \(\sqrt u=\sqrt v\) и, в частности, \(u\) и \(v\) коммутируют.

Следствие (сопряжённость степеней). Если \(w^i=uv\) при \(i\ge 1\), то существует разложение \(w=pq\) такое, что \((qp)^i=vu\); кроме того, примитивность произведения \(uv\) эквивалентна примитивности \(vu\).

О «теореме Шенкса—Штейнберга» и именовании Fine–Wilf

Я не знаю, какая именно формулировка подразумевается под названием «теорема Шенкса—Штейнберга» в контексте комбинаторики слов: в стандартных источниках по словам/строкам, доступных для проверки, это название не является устойчивым для классических утверждений о периодах или коммутирующих словах. Вместо этого в литературе устойчиво используются формулировки Fine–Wilf (periodicity lemma) и результаты Линдона—Шютценберже.

Также я не знаю надёжного первоисточника, где теорема Fine–Wilf о периодах называлась бы «теоремой Левенштейна»; в проверенных источниках она именуется Fine–Wilf (periodicity lemma / Fine and Wilf theorem).

Примеры, контрпримеры и упражнения с решениями

Короткие формальные примеры

Пример (коммутирование). Пусть \(A=\{a,b\}\), \(z=ab\), \(u=z^2=abab\), \(v=z^3=ababab\). Тогда \(uv=z^5=vu\). (Следует непосредственно из определения степеней.)

Контрпример (некоммутирование). При \(A=\{a,b\}\) слова \(u=a\), \(v=b\) не коммутируют: \(uv=ab\ne ba=vu\). (В свободном моноиде слово однозначно задаётся последовательностью букв.)

Пример (примитивный корень). Для \(u=(ab)^4\) примитивный корень равен \(\sqrt u=ab\), показатель \(4\). Единственность такого разложения гарантирована леммой о примитивном корне.

Контрпример к «слишком короткой» Fine–Wilf границе. Слово \(w=aba\) длины \(3\) имеет период \(2\) (так как \(w[1]=w[3]=a\)) и период \(3\) (вакуумно, поскольку \(n-p=0\)), но не имеет периода \(1\). Это согласуется с Fine–Wilf, поскольку при \(p=2\), \(q=3\), \(\gcd(p,q)=1\) требуется длина \(\ge 2+3-1=4\).

Упражнения с решениями

Упражнение 1. Пусть \(u,v\in A^+\) и \(uv=vu\). Докажите, что существует единственное примитивное \(p\in A^+\) такое, что \(u=p^m\) и \(v=p^n\) для некоторых \(m,n\ge 1\).

Решение. По лемме о коммутирующих словах \(\exists z\in A^+\): \(u=z^m\), \(v=z^n\). Пусть \(p=\sqrt z\). Тогда \(u=p^{m\cdot \alpha}\), \(v=p^{n\cdot \alpha}\) для некоторого \(\alpha\ge 1\). Единственность \(p\) следует из единственности примитивного корня. ∎

Упражнение 2. Пусть \(p\in A^+\) примитивно и пусть \(x\in A^\*\) таково, что \(xp=px\). Докажите, что \(x\in p^\*\).

Решение. Это ровно следствие о централизаторе примитивного слова: из \(xp=px\) следует, что \(x\) и \(p\) — степени одного слова; примитивность \(p\) форсирует совпадение этого слова с \(p\). ∎

Упражнение 3. Докажите лемму «граница \(\Leftrightarrow\) период»: \(w\) имеет период \(p\) тогда и только тогда, когда у \(w\) есть граница длины \(|w|-p\).

Решение. Приведено в разделе о границах и периодах. ∎

Упражнение 4. Пусть \(w\in A^+\) имеет периоды \(p\) и \(q\), и \(|w|\ge p+q-\gcd(p,q)\). Докажите, что \(\gcd(p,q)\) — период \(w\).

Решение. Приведено доказательство Fine–Wilf (версия для слов) через периодические продолжения и дискретный случай Fine–Wilf для последовательностей. ∎

Упражнение 5. Пусть \(u,v\in A^+\) и \(u\sim v\) (сопряжены). Докажите, что показатели в разложениях \(u=(\sqrt u)^m\), \(v=(\sqrt v)^n\) равны: \(m=n\), а примитивные корни \(\sqrt u\) и \(\sqrt v\) сопряжены.

Решение. Из \(u=pq\), \(v=qp\) следует, что циклический сдвиг не меняет периодическую структуру: если \(u=r^m\), то \(u\) периодично с периодом \(|r|\); сопряжение даёт тот же набор периодов для \(v\), поэтому \(v\) также является \(m\)-й степенью слова длины \(|r|\), причём примитивность корня сохраняется при циклическом сдвиге. Формально это фиксируется в стандартных леммах о сопряжённости и примитивных корнях. ∎

Упражнение 6. (Уравнение Линдона—Шютценберже.) Пусть \(a^m b^n=c^k\) в \(A^\*\), где \(m,n,k\ge 2\). Докажите, что решение тривиально: \(\exists w\in A^\*\) такое, что \(a,b,c\in w^\*\).

Решение. Это формулировка теоремы Линдона—Шютценберже о «periodicity forcing» уравнении (в свободных моноидах следует из результата для свободных групп, поскольку свободный моноид вкладывается в свободную группу). ∎

Литература и приоритет источников

Приоритет A (оригинальные статьи / первоисточники). (1) Натан Файн, Герберт Уилф. Uniqueness theorems for periodic functions (1965): исходная дискретная теорема о совпадении периодических последовательностей на длине \(h+k-\gcd(h,k)\) и оптимальность границы. (2) Роджер Линдон, Марсель-Поль Шютценберже. The equation \(a^M=b^N c^P\) in a free group (1962): первоисточник для семейства периодичность-форсирующих уравнений; доступность полного текста может зависеть от репозиториев, но результаты явно цитируются в современных обзорах и статьях. (3) Дональд Кнут, Джеймс Моррис, Вон Пратт. Fast Pattern Matching in Strings (1977): оригинальная статья для КМП; важна как источник мотивации структур «границы/префикс-функции», хотя в данном пособии алгоритм не требуется.

Приоритет B (классические монографии/учебники). (4) M. Lothaire. Applied Combinatorics on Words (распространяемая предварительная версия): содержит формулировку Fine–Wilf для периодов и стандартные леммы о примитивности/внутренних факторах. (5) Лекции по комбинаторике слов: заметки Ю. Кархумаки (Combinatorics of Words) содержат эквивалентности «коммутирование \(\Leftrightarrow\) степени общего слова», формулировки Fine–Wilf в форме через \(u^\omega\), а также стандартные следствия о примитивных корнях. (6) Теро Харью. Combinatorics on Words (конспект): базовые определения \(A^\*\), длины, операций со словами (как вводный источник).

Приоритет C (современные формализации и «канонические» источники формулировок). (7) Статья из LIPIcs (2025) фиксирует чёткие формулировки «первого» и «второго» результатов Линдона—Шютценберже (в терминах равенств \(xy=yx\) и \(xy=yz\)). (8) Штепан Холуб. Computing the Border Array in Isabelle/HOL (2022): формальные определения границ, периодических корней и связь с массивом границ, используемым в КМП. (9) Петер Дёмёши, Геза Хорват. Alternative Proof of the Lyndon–Schützenberger Theorem (2006): компактный источник формулировок леммы о коммутирующих словах, теоремы Fine–Wilf (в варианте через общие префиксы степеней) и единственности примитивного корня.

Русскоязычные вводные материалы (вспомогательные). (10) Конспект «Комбинаторика слов» (Просеминар, 2011) содержит определения алфавита, слова, степеней, примитивности, периодов и набор задач, совпадающих по тематике с настоящим пособием.