Слова Линдона. Лемма о конкатенации слов Линдона.

Слово Линдона (Lyndon word) — это непустое слово над упорядоченным алфавитом, которое лексикографически строго минимально среди всех своих собственных циклических сдвигов. В частности, слово Линдона является примитивным (не представимо в виде степени более короткого слова) и апериодичным. Эквивалентно, слово Линдона – единственное минимальное в лексикографическом порядке представителя своего класса конъюгаций (вращений). Это же равносильно тому, что при любом разложении \(w=uv\) с \(u,v\ne\varepsilon\) всегда \(u<v\). Главные результаты: (1) Лемма о конкатенации слов Линдона: если \(u\) и \(v\) – слова Линдона и \(u<v\), то \(uv\) также слово Линдона (к тому же \(uv<vu\)). (2) Стандартное разложение слова Линдона: любое слово Линдона \(w\) длины \(\ge2\) представляется как \(w=uv\), где \(u,v\) – слова Линдона и \(u<v\), причем такое разложение уникально (с точностью до выбора максимального суффикса \(v\)). (3) Факторизация Чен–Фокс–Линдона: любое (конечное) слово \(s\) над алфавитом единственным образом разбивается в конкатенацию \(s=s_1s_2\cdots s_k\), где все \(s_i\) – слова Линдона и \(s_1\ge s_2\ge \cdots \ge s_k\) в лексикографическом порядке. Такое разложение (иногда называемое факторизацией Линдона–Шенкса) строится жадно и единственно благодаря лемме о конкатенации. Далее будут даны формальные определения, теоремы и строгие доказательства этих результатов.

Определения

Алфавит \(\Sigma\) – конечное множество символов с заданным полным порядком.
Слово – конечная последовательность символов алфавита; множество всех слов обозначается \(\Sigma^*\), пустое слово – \(\varepsilon\). Длина слова \(w\) – \(|w|\).
Лексикографический порядок на \(\Sigma^*\) (по возрастанию) задан так: \(u<v\) если либо \(u\) – собственный префикс \(v\), либо при первом месте, где \(u\) и \(v\) различаются, символ из \(u\) меньше символа из \(v\) по порядку алфавита.
Префикс слова \(w=uv\) – слово \(u\) (в том числе \(u=\varepsilon\)). Суффикс – \(v\) (в том числе \(v=\varepsilon\)). Собственный префикс/суффикс – непустой, но не равный самому слову.
Циклический сдвиг слова \(w=xy\) (с ненулевой длиной \(x\)) – слово \(yx\). Два слова называются конъюгатами (цикл. перестановками) если одно получается из другого циклическим сдвигом.
Период слова – число \(p\) такое, что \(w[i]=w[i+p]\) для всех возможных \(i\). Граница слова – непустое слово, являющееся одновременно собственным префиксом и собственным суффиксом. Слово называется примитивным, если не представимо в виде \(u^k\) при \(k>1\), иначе – составным. Примитивность эквивалентна тому, что длина наименьшей границы равна нулю (слово не имеет ненулевой границы). Примитивное слово апериодично (не имеет меньшего периода, чем собственная длина).
Минимальный циклический сдвиг слова \(w\) – лексикографически наименьшее слово среди всех его циклических сдвигов. Если слово \(w\) является собственно наименьшим из своих циклических сдвигов, то его и называют словом Линдона.
Слово Линдона – непустое слово \(w\) такое, что \(w\) лексикографически строго меньше любых своих нетривиальных циклических сдвигов. Эквивалентно (и зачастую используемым) условиям:
\(w\) примитивно (не составное) и \(w\) – минимальный элемент в упорядочении всех его конъюгатов.
Для любого разложения \(w=uv\) с непустыми \(u,v\) выполняется \(w<v\), то есть \(u<v\).

В частности, слово Линдона лексикографически строго меньше любого своего собственного суффикса. Из этого сразу следует, что слово Линдона примитивно (поскольку в случае составного слова с периодом \(p<|w|\) его сдвиг на \(p\) позиций совпадал бы с ним, противоречие минимальности).

Лемма о конкатенации слов Линдона

Лемма. Если \(u\) и \(v\) – слова Линдона над тем же алфавитом и \(u<v\), то их конкатенация \(w=uv\) является словом Линдона. Более того, в этом случае \(uv<vu\) (либо эквивалентно \(uv\) минимально в своем классе конъюгатов).

Доказательство. Предположим \(u,v\) – Линдона и \(u<v\). Рассмотрим любое собственное суффикс-слово \(s\) конкатенации \(w=uv\). Есть два случая:

Случай 1: \(s\) находится полностью в \(v\), то есть \(s\) – суффикс \(v\). Так как \(v\) – слово Линдона, имеем \(v<s\). Поскольку \(u<v\), следует \(u\,v < v\) (нужно заметить, что при лексикографическом сравнении сначала сравниваются символы \(u\) и \(v\), и из \(u<v\) выводится \(uv<v\)). Далее, из неравенств \(uv<v\) и \(v<s\) по транзитивности лексикографического порядка получаем \(uv<s\).
Случай 2: \(|s|>|v|\), т.е. \(s\) начинается в \(u\) и продолжается в конце \(v\). Обозначим \(u = p q\), где \(q\ne\varepsilon\) – суффикс \(u\), такой что \(s = q v\). Поскольку \(u\) – Линдона, по аналогичному аргументу сравнения собственных суффиксов мы имеем \(u < q\). Тогда при сравнении \(uv = u v\) и \(s = q v\) первые символы различных составных частей будут сравниваться: первые символы \(u\) и \(q\); из \(u<q\) следует \(uv < qv = s\).

Во всех случаях \(uv<s\), значит \(uv\) меньше любого своего нетривиального суффикса. Таким образом \(uv\) – слово Линдона. Наконец, заметим, что при \(u<v\) при сравнивании слов \(uv\) и \(vu\) на первом символе (первый символ \(u\) против первого символа \(v\)) уже получаем \(uv<vu\).

Следствие. Обратное также верно: если \(u,v\) – слова Линдона и \(uv\) слово Линдона, то обязательно \(u<v\). В самом деле, если бы \(v \le u\), то при лексикографическом сравнении \(uv\) с циклическим сдвигом \(vu\) первый символ \(v\) не больше первого символа \(u\), и \(vu \le uv\), что противоречит минимальности \(uv\). Кроме того, из того, что \(uv\) Линдона следует, как и выше, что \(u\) и \(v\) сами должны быть Линдона (иначе их собственные суффиксы дали бы более мелкий суффикс \(uv\)), так что можно сформулировать эквивалентную версию: \(uv\) – слово Линдона тогда и только тогда, когда \(u,v\) Линдона и \(u<v\).

Стандартное разложение слова Линдона

Теорема (Стандартное разложение). Любое слово Линдона \(w\) длины \(|w|\ge2\) можно (единственным образом) представить в виде конкатенации двух слов Линдона \(w = u v\), где \(v\) – лексикографически наименьший собственный суффикс \(w\) (или, эквивалентно, \(v\) – наибольший по длине собственный суффикс, который является словом Линдона), а \(u\) – начальная часть. В этом разложении обязательно \(u<v\).

Доказательство (эскиз). Пусть \(w\) – слово Линдона. Рассмотрим среди всех собственных суффиксов \(w\) такие, которые сами являются словами Линдона. Поскольку отдельный символ – слово Линдона, существует хотя бы один собственный Линдон-суффикс. Из них выберем самый длинный по длине \(v\). Тогда по определению \(v\) является собственным суффиксом \(w\) и слово Линдона, а оставшаяся часть \(u\) (так что \(w=uv\)) по построению либо пустая либо образует слово Линдона. Если \(u\) пусто, то \(w=v\) и мы бы выбрали \(u=v=w\), что противоречит \(|w|\ge2\). Значит \(u\neq\varepsilon\). Если бы \(u\) не было словом Линдона, то \(u\) имело бы собственный суффикс \(u'\) и \(u'<u\); тогда \(u'v\) был бы собственным суффиксом \(w\) и строкой Линдона (так как \(u'\) и \(v\) — Линдона и \(u'<u<v\) по лемме о конкатенации даёт \((u')v\) Линдона), что противоречит максимальности \(v\). Таким образом и \(u\) – слово Линдона. Остаётся заметить, что из \(u\) и \(v\) Линдона и \(uv=w\) сразу следует \(u<v\) (иначе \(vu\) был бы циклическим сдвигом \(w\) меньшим него). Единственность такого разложения обеспечивается тем, что \(v\) был выбран максимально возможным; если бы существовало другое разложение \(w=u'v'\) с \(v'\) линдон и \(v'\ne v\), то один из суффиксов длины больше \(|v|\) также был бы линдон, что противоречит выбору \(v\).

Факторизация Чен–Фокс–Линдона (единственность разложения)

Теорема (Chen–Fox–Lyndon, 1958). Любое непустое слово \(s\) над алфавитом единственным образом раскладывается в конкатенацию неростоющей (невозрастающей) последовательности слов Линдона:

\[ s = s_1 s_2 \cdots s_k, \]

где каждое \(s_i\) – слово Линдона, и \(s_1 \ge s_2 \ge \cdots \ge s_k\) (лексикографически). Такое разложение называют факторизацией Линдона. При этом последнее слово \(s_k\) лексикографически минимальный суффикс \(s\).

Доказательство (существования). Доказательство стандартное. Заметим, что единичные символы – слова Линдона, следовательно любое слово можно разбить на слова Линдона. Возьмём среди всех разложений \(s=s_1\cdots s_k\) с \(s_i\) Линдона такое, в котором \(k\) минимально. Докажем, что тогда автоматически \(s_1 \ge s_2 \ge \cdots \ge s_k\). Действительно, если бы имелся индекс \(i\) такой, что \(s_i < s_{i+1}\), то по лемме о конкатенации слова \(s_i s_{i+1}\) были бы Линдона, и мы могли бы заменить в разложении две составляющие на одну, уменьшив \(k\). Это противоречит минимальности выбора. Значит искомая факторизация существует и её слова уже упорядочены невозрастающе.

Доказательство (единственности). Предположим, существуют два разложения с теми же свойствами:

\[ s = s_1 s_2 \cdots s_k = s'_1 s'_2 \cdots s'_\ell,\qquad s_1\ge\cdots\ge s_k,\; s'_1\ge\cdots\ge s'_\ell, \]

где все \(s_i,s'_j\) – Lyndon. Покажем, что \(s_1 = s'_1\). Пусть без ограничения длины считать \(|s_1|\le|s'_1|\). Тогда \(s'_1\) начинается с \(s_1\) (иначе на первой позиции разложений встретятся разные буквы и меньшая лексикографически слагаемая отстает). Если \(|s_1|<|s'_1|\), то \(s'_1 = s_1 t\) с ненулевым \(t\). Поскольку \(s'_1\) – Линдона, при любом разложении \(s'_1 = uv\) должен выполняться \(u<v\). В частности, при \(u=s_1\), \(v=t\) получаем \(s_1 < t\). Но тогда \(s'_1 = s_1 t\) — конкатенация двух Линдона (так как \(s_1\) – Линдона и \(t\) является суффиксом \(s'_1\) и потому также Линдона) с \(s_1 < t\), что по лемме даёт \(s'_1\) слово Линдона. Однако тогда разложение \(s = (s_1 t) s_2 \cdots s_k\) имело бы количество членов меньше, чем \(s = s_1 (t s_2) \cdots s_k\), что невозможно. Поэтому \(|s_1| = |s'_1|\) и \(s_1=s'_1\). Аналогичным рассуждением последовательно показываем совпадение всех последующих факторов. Таким образом разложение однозначно.

Указанные теоремы и леммы полностью характеризуют «лексикографическую» структуру разложений слов и лежат в основе алгоритма Дюваля для поиска такого разложения.

Замечания и обобщения

Варианты формулировок: Как видно, понятие слова Линдона эквивалентно нескольким формулировкам: (i) «минимальное среди циклических сдвигов», (ii) «меньше любого своего собственного суффикса», (iii) «при любом разбиении \(w=uv\) с \(u,v\ne\varepsilon\) выполняется \(u<v\)». Эти формулировки часто используются взаимозаменяемо.
Связь с декомпозициями: Факторизация Чен–Фокс–Линдона характеризует единственное невозрастающее разложение в слова Линдона. Любая другая лексикографически невозрастающая разложение однозначно совпадает с факторизацией Линдона.
Дополнительные обобщения (необязательное расширение): Аналогичные свойства и разложения существуют для бесконечных слов (теорема Канова-Рота, факторизация по словам Линдона для бесконечных последовательностей) и могут быть рассмотрены для полурегулярного лексикографического порядка на алфавите.

Таблица: сравнение близких формулировок

Утверждение	Формулировка	Условия	Следствия
Определение слова Линдона (циклический)	\(w\) непустое, лекс. меньше всех своих собственных циклических сдвигов (конъюгатов).	\(w\in\Sigma^+\)	\(w\) примитивно, апериодично
Определение слова Линдона (суффиксное)	\(w\) непусто и для любого разбиения \(w=uv\) (\(u,v\ne\varepsilon\)) выполняется \(w<v\) (или \(u<v\)).	\(w\in\Sigma^+\)	эквивалентно предыдущему определению
Лемма о конкатенации (прямое)	Если \(u,v\) – слова Линдона и \(u<v\), то слово \(uv\) – Линдона (при этом \(uv<vu\)).	\(u,v\in\Sigma^+\), Линдона; \(u<v\)	\(uv\) – Линдона, \(uv<vu\)
Лемма о конкатенации (эквивалентность)	\(uv\) – Линдона тогда и только тогда, когда \(u,v\) – Линдона и \(u<v\).	\(u,v\in\Sigma^+\), Линдона	двунаправленное условие
Стандартная факторизация Линдона	Любое Линдона-слово \(w\) (\(\lvert w\rvert\ge 2\)) раскладывается как \(w=uv\), где \(u,v\) — слова Линдона, \(u<v\), а \(v\) — лексикографически наименьший суффикс.	\(w\in\Sigma^+\), Линдона	разложение существует и единственно
Теорема факторизации Чен–Фокс–Линдона	Любое слово \(s\) раскладывается единственно как \(s=s_1s_2\cdots s_k\), где \(s_i\) – Линдона, \(s_1\ge\cdots\ge s_k\). Последнее \(s_k\) – наименьший суффикс \(s\).	\(s\in\Sigma^+\)	единственность лексикографически невозрастающей факторизации

Каждое из приведённых утверждений доказано в источниках и приведено здесь в строгой формулировке. Указаны необходимые и достаточные условия, а также последствия формулировок.

Источники: результаты Линдона и др. изложены в классических трудах по комбинаторике слов (см. например , англ.) и учебниках (Lothaire и др.), а также в работах Чена–Фокса–Линдона. Оригинальные статьи: Lyndon (1954), Shirshov (1953) по введению «регулярных слов», и Chen–Fox–Lyndon (1958) – для факторизации. В таблице приведены ссылки на учебный пересказ этих результатов. (При необходимости допускается сравнение формулировок в разных источниках.)