Линдон слово

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

Определения

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

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

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

Другая характеристика такова: слово Линдона обладает тем свойством, что оно непусто, и всякий раз, когда оно разбивается на две непустые подстроки, левая подстрока всегда лексикографически меньше правой подстроки. То есть, если $w$ это слово Линдона, и $w=uv$ — это любая факторизация на две подстроки, при этом $u$ и $v$ понимается как непустое, то $u<v$. Это определение подразумевает, что строка $w$ длины $\geq 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$.
2. Пока последний символ $x$ — последний символ в отсортированном алфавите, удалите его, получив более короткое слово.
3. Замените последний оставшийся символ $x$ его преемником в отсортированном порядке алфавита.

Например, предположим, что мы сгенерировали двоичные слова Линдона длиной до 7, и мы сгенерировали до $w=00111$, то шаги следующие:

1. Повторите и обрежьте, чтобы получить $x=00111\;00{\cancel {111}}$
2. Поскольку последний символ равен 0, это не последний символ.
3. Увеличьте последний символ, чтобы получить $x=00111\;01$.

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

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

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

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

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

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

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

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

1. Пусть m будет индексом символа-кандидата, который будет добавлен к уже собранным символам. Изначально m = 1 (индексы символов в строке начинаются с нуля).
2. Пусть 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] к текущим собранным символам, мы получим слово Линдона. Но мы пока не можем добавить его в список результатов, поскольку оно может быть лишь частью более крупного слова Линдон. Таким образом, просто увеличьте 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 над полем $\mathbb {F} _{p}$ равно числу слов Линдона длины d в алфавите из p символов; их можно поместить в явную переписку.

Теорема Рэдфорда утверждает, что тасованную алгебру над полем характеристики 0 можно рассматривать как полиномиальную алгебру над словами Линдона. Точнее, пусть A — алфавит, пусть k — поле характеристики 0 (или, в более общем смысле, коммутативное поле $\mathbb {Q}$-алгебра), и пусть R — свободная некоммутативная k -алгебра k ⟨ x _a | а ∈ А ⟩ . Тогда слова над A можно отождествить с «некоммутативными мономами» (т. е. произведениями x _a ) в R ; а именно, мы отождествляем слово ( a ₁ , a ₂ ,..., ) _an с мономом x _{a 1} x _{a 2} ... x _{a n} . Таким образом, слова над A образуют базис k -векторного пространства R . Затем тасованный продукт определяется на R ; это k -билинейное, ассоциативное и коммутативное произведение, которое обозначается ш и которое по словам можно рекурсивно определить как

1 ш v = v for any word v ;

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

ua ø vb знак равно ( u ø vb ) a + ( ua ø v ) b для любых a , b ∈ A и любых слов u и v .

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

См. также

• Лексикографически минимальное вращение строки
• Морфическое слово
• Штурмовское слово
• Ожерелье (комбинаторика)

Ссылки

• Берстель, Жан; Перрен, Доминик (2007), «Истоки комбинаторики слов» (PDF) , European Journal of Combinatorics , 28 (3): 996–1022, doi : 10.1016/j.ejc.2005.07.019 , MR   2300777 .
• Берстель, Дж.; Покчиола, М. (1994), «Средняя стоимость алгоритма Дюваля для генерации слов Линдона» (PDF) , Theoretical Computer Science , 132 (1–2): 415–425, doi : 10.1016/0304-3975(94)00013- 1 , МР   1290554 .
• Брлек, С.; Лашо, Ж.-О.; Провансаль, X.; Ройтенауэр, К. (2009), «Линдон + Кристоффель = цифровая выпуклость» (PDF) , Распознавание образов , 42 (10): 2239–2246, Бибкод : 2009PatRe..42.2239B , doi : 10.1016/j.patcog.2008.11. 010 .
• Чен, К.-Т.; Фокс, Р.Х. ; Линдон, Р.К. (1958), «Свободное дифференциальное исчисление. IV. Факторгруппы нижнего центрального ряда», Annals of Mathematics , 2nd Ser., 68 (1): 81–95, doi : 10.2307/1970044 , JSTOR   1970044 , МР   0102539 .
• Дюваль, Жан-Пьер (1983), «Факторизация слов по упорядоченному алфавиту», Journal of Algorithms , 4 (4): 363–381, doi : 10.1016/0196-6774(83)90017-2 .
• Дюваль, Жан-Пьер (1988), «Генерация раздела классов спряжения и дерево слов Линдона ограниченной длины», Theoretical Computer Science (на французском языке), 60 (3): 255–283, doi : 10.1016 / 0304-3975 (88)90113-2 , МР   0979464 .
• Фредриксен, Гарольд; Майорана, Джеймс (1978), «Ожерелья из бус k цветов и k -арных последовательностей де Брейна», Discrete Mathematics , 23 (3): 207–210, doi : 10.1016/0012-365X(78)90002-X , MR   0523071 .
• Гил, Дж.; Скотт, Д.А. (2009), Преобразование сортировки биективных строк (PDF) .
• Глен, Эми (2012), «Комбинаторика слов Линдона» (PDF) , Мини-конференция: Комбинаторика, представления и структура лиева типа , Мельбурнский университет
• Голомб, Соломон В. (1969), «Неприводимые полиномы, синхронизирующие коды, примитивные ожерелья и круговая алгебра», в Бозе, RC; Даулинг Т.А. (ред.), Комбинаторная математика и ее приложения: материалы конференции, состоявшейся в Университете Северной Каролины в Чапел-Хилл, 10–14 апреля 1967 г. , серия монографий Университета Северной Каролины по вероятности и статистике, том. 4, University of North Carolina Press, стр. 358–370, ISBN.  9780807878200 , OCLC   941682678
• Хольвег, Кристоф; Ройтенауэр, Кристоф (2003), «Слова, перестановки и деревья Линдона» (PDF) , Theoretical Computer Science , 307 (1): 173–8, doi : 10.1016/S0304-3975(03)00099-9
• Куфлейтнер, Манфред (2009), «О биективных вариантах преобразования Берроуза-Уиллера », Голуб, январь; Ждярек, Ян (ред.), Пражская конференция по стрингологии , стр. 65–69, arXiv : 0908.0239 , Bibcode : 2009arXiv0908.0239K .
• Лотер, М. (1983), Комбинаторика слов , Энциклопедия математики и ее приложений, том. 17, издательство Addison-Wesley Publishing Co., Ридинг, Массачусетс, ISBN  978-0-201-13516-9 , МР   0675953
• Линдон, Р.К. (1954), «О проблеме Бернсайда», Труды Американского математического общества , 77 (2): 202–215, doi : 10.2307/1990868 , JSTOR   1990868 , MR   0064049 .
• Мартин, М.Х. (1934), «Проблема в аранжировках», Бюллетень Американского математического общества , 40 (12): 859–864, doi : 10.1090/S0002-9904-1934-05988-3 , MR   1562989 .
• Мелансон, Гай (1992), «Комбинаторика деревьев Холла и слов Холла» (PDF) , Журнал комбинаторной теории , серия A, 59 (2): 285–308, doi : 10.1016/0097-3165(92)90070-B
• Мелансон, Г. (2001) [1994], «Линдоновское слово» , Энциклопедия математики , EMS Press
• Мелансон, Ги; Ройтенауэр, Кристоф (1989), «Слова Линдона, свободные алгебры и перетасовки», Canadian Journal of Mathematics , 41 (4): 577–591, doi : 10.4153/CJM-1989-025-2 , S2CID   17395250
• Раски, Фрэнк (2003), Информация об ожерельях, словах Линдона, последовательностях Де Брейна , заархивировано из оригинала 02 октября 2006 г.
• Шютценбергер, член парламента ; Шерман, С. (1963), «О формальном произведении сопряженных классов в свободной группе», Журнал математического анализа и приложений , 7 (3): 482–488, doi : 10.1016/0022-247X(63)90070- 2 , МР   0158002 .
• Шютценбергер, член парламента (1965), «О факторизации свободных моноидов», Труды Американского математического общества , 16 (1): 21–24, doi : 10.2307/2033993 , JSTOR   2033993 , MR   0170971 .
• Ширшов А.И. (1953), "Подалгебры свободных алгебр Ли", Матем. Сборник , Новая серия, 33 (75): 441–452, МР   0059892
• Ширшов А.И. (1958), "О свободных кольцах Ли", Матем. Сборник , Новая серия, 45 (87): 113–122, МР   0099356
• Рэдфорд, Дэвид Э. (1979), «Естественный кольцевой базис для тасованной алгебры и приложение к групповым схемам», Journal of Algebra , 58 (2): 432–454, doi : 10.1016/0021-8693(79)90171 -6 .