Слово Линдона — это непустая строка, которая строго меньше в лексикографическом порядке, чем все её вращения. Слова Линдона названы в честь математика , который исследовал их в 1954 году, называя их стандартными лексикографическими последовательностями. Анатолий Ширшов ввёл cлова Линдона в 1953 году, называя их регулярными словами. Слово Линдона являются частным случаем . Почти все свойства слов Линдона присущи и словам Холла.

Определения Существует несколько эквивалентных определений.

Слово Линдона длины над алфавитом размера — это строка из символов, содержащая буквы данного алфавита, при этом строка является единственным минимальным элементом в мультимножестве всех его вращений, упорядоченном в лексикографическом порядке. То, что она является единственным наименьшим вращением, означает, что слово Линдона отличается от любого из своих нетривиальных вращений и, следовательно, апериодично.

Иначе говоря, слово является словом Линдона тогда и только тогда, когда оно непусто и лексикографически строго меньше любого из своих собственных суффиксов, то есть, для всех непустых слов таких, что и непусто.

Другое определение: Слово Линдона не пустое и, когда оно разбивается на две непустые подстроки, левая подстрока всегда лексикографически меньше правой. То есть, если — слово Линдона и — любое разложение на две непустые подстроки, то . Это определение подразумевает, что строка длиной является словом Линдона тогда и только тогда, когда существуют слова Линдона и такие, что и . Хотя может существовать более одного выбора и с этим свойством, существует особый выбор, называемый стандартным разложением, в котором максимально возможной длины.

Перечисление Слова Линдона над двухсимвольным бинарным алфавитом {0,1}, упорядоченные по длине, а затем лексикографически в пределах каждого класса длины, образуют бесконечную последовательность, которая начинается так: 0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ... Первая строка, не входящая в эту последовательность, «00», опущена, поскольку она периодична (состоит из двух повторений подстроки «0»). Вторая опущенная строка, «10», апериодична, но не является минимальной в своем классе перестановок, так как её можно циклически переставить в (лексикографически) меньшую строку «01».

Пустая строка также соответствует определению слова Линдона нулевой длины. Количество бинарных слов Линдона каждой длины, начиная с нулевой, образует целочисленную последовательность 1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... Слова Линдона соответствуют представителям апериодического класса ожерелий и, следовательно, могут быть подсчитаны с помощью функции Моро подсчёта ожерелий.

Генерация Дюваль предоставил эффективный алгоритм перечисления слов Линдона с длиной, не превосходящей с заданным размером алфавита в лексикографическом порядке. Если является одним из слов в последовательности, то следующее слово можно найти после следующих действий: Повторяем и укорачиваем получившееся слово , чтобы оно содержало ровно символов. Если последний символ строки является последним символом алфавита, удаляем его, создавая более короткое слово. Заменяем последний символ в строке на следующий по порядку в алфавите. Например, предположим, мы генерируем бинарные слова Линдона длиной 7, и мы сгенерировали до , тогда шаги следующие:

Повторяем и укорачиваем, получаем Поскольку последний символ равен 0, он не является финальным. Увеличиваем последний символ и получаем .

Наихудшее время для генерации слова, следующего в последовательности за , по данной процедуре составляет . Однако, если генерируемые слова хранятся в массиве длиной , и построение нового слова из выполняется путём добавления символов в конец а не путём создания полной копии , то среднее время генерации слова, следующего за (при условии равновероятности каждого слова), становится константой. Следовательно, всю последовательность слов Линдона длиной не более можно сгенерировать за время, пропорциональное длине самой последовательности.

Стандартное разложение Согласно любая строка может быть образована единственным способом путём соединения слова Линдона, в котором слова в последовательности лексикографически не возрастают . Последнее слово Линдона в этой последовательности является лексикографически наименьшим суффиксом заданной строки. Факторизация в невозрастающую последовательность слов Линдона (так называемая факторизация Линдона) может быть построена за линейное время. Факторизации Линдона могут использоваться как часть биективного варианта преобразования Барроуза — Уилера для сжатия данных, а также в алгоритмах .

Такие разложения можно представить (единственным образом) в виде конечных бинарных деревьев. Листья таких деревьев помечены символами алфавита, а каждое правое ответвление соответствует последнему слову Линдона в последовательности. Эти деревья иногда называют стандартными скобочными выражениями и могут использоваться как разложения элементов свободной группы или как базисные элементы свободной алгебры Ли. Данные деревья являются частным случаем (так как слова Линдона являются частным случаем слов Холла), и, соответственно, слова Холла задают стандартный порядок, называемый для групп, и базис для алгебр Ли. Фактически, они предоставляют явную конструкцию для коммутаторов, встречающихся в теореме Пуанкаре — Биркгофа — Витта, необходимой для построения универсальных обёртывающих алгебр.

Любое слово Линдона можно рассматривать как перестановку, называемую стандартной суффиксной перестановкой.

Алгоритм Дюваля Дюваль разработал алгоритм поиска стандартного разложения, который работает за линейное время и использует постоянный объём памяти. Он проходит по строке, пытаясь найти максимально длинное слово Линдона. Найдя такое слово, он добавляет его в список результатов и продолжает поиск в оставшейся части строки. Полученный список строк является стандартным разложением данной строки. Более формальное описание алгоритма приведено ниже.

Для заданной строки S длины N следует выполнить следующие шаги: Пусть m будет индексом символа-кандидата, который будет добавлен к уже собранным символам. Изначально m = 1 (индексы символов в строке начинаются с нуля). Пусть k будет индексом символа, с которым мы будем сравнивать остальные. Изначально k = 0. Пока k и m меньше N, сравниваем S[k] (k-й символ строки S) с символом S[m]. Возможны три исхода: Если S[k] равен S[m], добавляем S[m] к текущим собранным символам. Увеличиваем k и m. Если S[k] меньше S[m], мы могли бы добавить S[m] к текущим собранным символам и получить слово Линдона. Но сделать это мы пока не можем, поскольку это слово может быть частью более крупного слова Линдона. Поэтому просто увеличиваем m и устанавливаем k в 0, так что следующий символ будет сравниваться с первым символом в строке. Если S[k] больше S[m], мы не можем добавить S[m] к собранным символам, поскольку результат не будет словом Линдона и не будет началом другого слова. Поэтому добавляем первые m−k собранных символа к списку результатов, удалив их из строки, устанавливаем m в 1 и k в 0, чтобы они указывали на второй и первый символ строки соответственно. Если m > N, это по сути то же самое, что столкнуться с минус бесконечностью, поэтому добавим первые m−k собранных символа в список результатов после удаления их из строки, устанавливаем m в 1 и k в 0, и возвращаемся к предыдущему шагу. Добавляем S в список результатов.

Связь с последовательностями де Брёйна Если объединить в лексикографическом порядке все слова Линдона, длина которых делит заданное число n, получится последовательность де Брёйна, циклическая последовательность символов, в которой каждая возможная подпоследовательность длины n встречается ровно один раз как одна из подпоследовательностей. Например, конкатенация двоичных слов Линдона, длины которых делят число четыре, даёт 0 0001 0011 01 0111 1 Эта конструкция, наряду с эффективным порождением слов Линдона, обеспечивает эффективный метод построения определённой последовательности де Брёйна за линейное время, используя .

Дополнительные свойства и приложения Слова Линдона имеют приложение в описании свободных алгебр Ли, в частности, для построения базиса однородной части заданной степени. Именно это изначально побудило Линдона ввести данные слова. Слова Линдона можно рассматривать как частный случай .

Для простого p количество неприводимых нормированных многочленов степени d над полем совпадает с количеством слов Линдона длины d в алфавите из p символов; между ними можно установить явное соответствие.

Теорема Рэндофа утверждает, что над полем характеристики 0 может быть представлена как полиномиальная алгебра над словами Линдона. Точнее, пусть A — алфавит, пусть k — поле характеристики 0 (или, в более общем случае, коммутативная -алгебра), а R — свободная некоммутативная k-алгебра . Слова над A можно отождествить с «некоммутативными одночленами» (то есть произведениями xa) в R, а именно, слово отождествляется с одночленом . Таким образом, слова над A образуют базис k-векторного пространства R. Затем на R определяется шафл-произведение — это k-билинейное, ассоциативное и коммутативное произведение, обозначаемое символом «ш», которое для слов может быть рекурсивно определено следующим образом: 1 ш v = v для любого слова v; u ш 1 = u для любого слова u; ua ш vb = (u ш vb)a + (ua ш v)b         для любых и любых слов u и v. Шафл-алгебра над алфавитом A определяется как аддитивная группа R , наделённая операцией ш в качестве умножения. Теорема Редфорда утверждает, что слова Линдона являются алгебраически независимыми элементами этой шафл-алгебры и порождают её. Следовательно, шафл-алгебра изоморфна кольцу многочленов над k, где переменные соответствуют словам Линдона.

См. также

Слово Штурма Ожерелье (комбинаторика)

Примечания

Литература

.

.

.

Категория:Комбинаторика слов