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

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

Определения

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

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

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

Другая характеристика заключается в следующем: слово Линдона обладает тем свойством, что оно непусто, и всякий раз, когда оно разбивается на две непустые подстроки, левая подстрока всегда лексикографически меньше правой подстроки. То есть, если ш это слово Линдона, и ш = УФ - любая факторизация на две подстроки с ты и v понимается как непустой, тогда ты < v. Это определение подразумевает, что строка ш длины ≥ 2 является словом Линдона тогда и только тогда, когда существуют слова Линдона ты и v такой, что ты < v и ш = УФ.^[4] Хотя может быть более одного выбора ты и v с этим свойством есть особый выбор, называемый стандартная факторизация, в котором v как можно дольше.^[5]

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

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

Слова Линдона соответствуют апериодическим ожерелье представителей класса и, таким образом, могут считаться Функция подсчета ожерелий Моро.^[3]^[6]

Поколение

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

Повторите символы из ш сформировать новое слово Икс длины ровно п, где яй символ Икс совпадает с символом в позиции (я длина мода (ш)) из ш.
Пока последний символ Икс является последним символом в отсортированном порядке алфавита, удалите его, чтобы получить более короткое слово.
Замените последний оставшийся символ Икс его преемником в отсортированном порядке алфавита.

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

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

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

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

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

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

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

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

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

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

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

0 0001 0011 01 0111 1

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

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

Слова Lyndon имеют приложение к описанию свободные алгебры Ли, при построении основы для однородной части данной степени; это было первоначальной мотивацией Линдона ввести эти слова.^[4] Слова Lyndon можно понимать как частный случай Прихожие.^[4]

Для премьер п, количество неприводимых монические полиномы степени d над полем ${ displaystyle mathbb {F} _ {p}}$ равно количеству слов Линдона длины d в алфавите п символы; они могут быть помещены в явное соответствие.^[17]

Теорема Рэдфорда утверждает, что перемешать алгебру над полем характеристики 0 можно рассматривать как алгебру полиномов над словами Линдона. Точнее, пусть А быть алфавитом, пусть k - поле характеристики 0 (или, более общо, коммутативная ℚ-алгебра), и пусть р быть свободным некоммутативным k-алгебра k ⟨ Икс_а | а ∈ А ⟩. Слова закончились А затем можно отождествить с «некоммутативными мономами» (т. е. произведениями Икс_а) в р; а именно, мы отождествляем слово (а₁,а₂,...,а_п) с мономом Икс_а₁Икс_а₂...Икс_{а_п}. Таким образом, слова закончились А сформировать k-векторно-пространственная основа р. Затем перемешать продукт определяется на р; это k-билинейное, ассоциативное и коммутативное произведение, которое обозначается ш и которое на словах может быть рекурсивно определено как

1 ш v = v для любого слова v;

ты ø 1 = ты для любого слова ты;

ua ш vb = (ты ш vb)а + (ua ш v)б для любого а,б ∈ A и любых слов ты и v.

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

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

Примечания

^ Линдон (1954).
^ Ширшов (1953).
^ ^а ^б Берстель и Перрин (2007); Мелансон (2001).
^ ^а ^б ^c Мелансон (2001).
^ Берстель и Перрин (2007).
^ Руски (2003) предоставляет подробные сведения об этих подсчетах слов Линдона и нескольких связанных концепциях.
^ Берстель и Поккиола (1994).
^ Мелансон (2001). Берстель и Перрин (2007) напишите, что хотя это обычно приписывается Чен, Фокс и Линдон (1958), и следует из результатов этой статьи, это не было заявлено явно до тех пор, пока Шютценбергер (1965). Он был сформулирован явно Ширшов (1958), видеть Шютценбергер и Шерман (1963).
^ ^а ^б Дюваль (1983).
^ Гил и Скотт (2009); Куфлейтнер (2009).
^ Brlek et al. (2009).
^ Эми Глен "Комбинаторика слов Линдона " (2012)
^ Гай Мелансон, (1992) "Комбинаторика холловских деревьев и холловских слов ", Журнал комбинаторной теории, 59A(2) С. 285–308.
^ Гай Мелансон и Кристоф Ройтенауэр (1989), «Слова Линдона, свободные алгебры и тасования», Канадский математический журнал. 41, No. 4, pp. 577-591.
^ Кристоф Хольвег и Кристоф Ройтенауэр "Слова Линдона, перестановки и деревья ", (2003) LaCIM
^ В соответствии с Берстель и Перрин (2007), последовательность, сгенерированная таким образом, была впервые описана (с другим методом генерации) Мартин (1934), а связь между ним и словами Линдона была замечена Фредриксен и Майорана (1978).
^ Соломон В. Голомб (1969) "Неприводимые полиномы, синхронизирующие коды, примитивные ожерелья и круговая алгебра", Proc. Conf Комбинаторная математика и ее приложения, стр.358--370 (Университет Северной Каролины).
^ ^а ^б Рэдфорд (1979)