Линдон слово - Lyndon word

В математике , в области комбинаторики и информатики , слово Линдона непустая строка , которая строго меньше в лексикографическом порядке , чем все его вращений . Слова Линдона названы в честь математика Роджера Линдона , который исследовал их в 1954 году и назвал их стандартными лексикографическими последовательностями . Анатолий Ширшов ввел слова Линдона в 1953 году, назвав их обычными словами . Слова Линдона - это частный случай слов Холла ; почти все свойства слов Линдона разделяются словами Холла.

Определения

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

К -ичного Линдон слово длины п > 0 является п -character строки над алфавитом размером к , и который является уникальным минимальным элементом в лексикографическом упорядочении в мультимножестве всех его вращений. Особо наименьшее вращение означает, что слово Линдона отличается от любого из его нетривиальных вращений и, следовательно, является апериодическим.

С другой стороны, слово w является словом Линдона тогда и только тогда, когда оно непусто и лексикографически строго меньше любого из его собственных суффиксов, то есть w  <  v для всех непустых слов v таких, что w  =  uv и u непусто.

Другая характеристика заключается в следующем: слово Линдона обладает тем свойством, что оно непусто, и всякий раз, когда оно разбивается на две непустые подстроки, левая подстрока всегда лексикографически меньше правой подстроки. То есть, если w - слово Линдона, а w  =  uv - любая факторизация на две подстроки, при этом u и v считаются непустыми, то u  <  v . Из этого определения следует, что строка w длины ≥ 2 является словом Линдона тогда и только тогда, когда существуют слова Линдона u и v такие, что u  <  v и w  =  uv . Хотя может быть более одного выбора u и v с этим свойством, существует особый выбор, называемый стандартной факторизацией , в котором v является максимально длинным.

Перечисление

Слова Линдона в двухсимвольном двоичном алфавите {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, ... (последовательность A001037 в OEIS )

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

Поколение

Дюваль (1988) предлагает эффективный алгоритм для перечисления слов Линдона длины не более n с заданным размером алфавита s в лексикографическом порядке . Если w - одно из слов в последовательности, то следующее слово после w можно найти, выполнив следующие действия:

  1. Повторите символы из w, чтобы сформировать новое слово x длины точно n , где i- й символ x совпадает с символом в позиции ( i mod length ( w )) слова w .
  2. Пока последний символ x является последним символом в отсортированном порядке алфавита, удалите его, получив более короткое слово.
  3. Замените последний оставшийся символ x его преемником в отсортированном порядке алфавита.

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

Стандартная факторизация

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

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

Каждое слово Lyndon можно понимать как перестановку , стандартную перестановку суффиксов .

Алгоритм Дюваля

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

Для строки S длины N следует выполнить следующие шаги:

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

Связь с последовательностями де Брейна

Если объединить вместе в лексикографическом порядке все слова Линдона, длина которых делит данное число n , результатом будет последовательность де Брейна , круговая последовательность символов, такая, что каждая возможная последовательность длины n появляется ровно один раз как одна из своих смежные подпоследовательности. Например, объединение двоичных слов Линдона, длина которых делит четыре, имеет вид

0 0001 0011 01 0111 1

Эта конструкция, вместе с эффективной генерацией слов Линдона, обеспечивает эффективный метод построения конкретной последовательности де Брейна в линейном времени и логарифмическом пространстве .

Дополнительные свойства и приложения

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

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

Теорема Рэдфорда утверждает, что тасовая алгебра над полем характеристики 0 может рассматриваться как полиномиальная алгебра над словами Линдона. Точнее, пусть быть алфавитом, пусть к быть поле характеристики 0 (или, более общих, коммутативная алгебра), и пусть R свободный некоммутативными к -алгебра кх | . Слова над A затем можно отождествить с «некоммутативными одночленами» (т. Е. Произведениями x a ) в R ; а именно, мы отождествляем слово ( a 1 , a 2 , ..., a n ) с одночленом x a 1 x a 2 ... x a n . Таким образом, слово над А образует к -векторному пространству базиса R . Затем на R определяется перемешанное произведение ; это k -билинейное, ассоциативное и коммутативное произведение, которое обозначается ш и которое на словах может быть рекурсивно определено как

1 ш v = v для любого слова v ;
u 1 = u для любого слова u ;
ua ø vb = ( u ø vb ) a + ( ua ø v ) b для любых a , b ∈ A и любых слов u и v .

Перетасовка алгебра в алфавите А определяется аддитивная группа R наделена ш в качестве умножения. Теорема Рэдфорда теперь утверждает, что слова Линдона являются алгебраически независимыми элементами этой тасовой алгебры и порождают ее; таким образом, алгебра тасования изоморфна кольцу многочленов над k с неопределенными, соответствующими словам Линдона.

Смотрите также

Примечания

использованная литература