слово Линдона
Строка, которая строго меньше в лексикографическом порядке, чем все ее вращения

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

Определения

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

-арное слово Линдона длины - это строка символов в алфавите размера , и которая является уникальным минимальным элементом в лексикографическом порядке в мультимножестве всех его вращений. Будучи единственным наименьшим вращением, подразумевает, что слово Линдона отличается от любого из своих нетривиальных вращений, и, следовательно, является апериодическим. [3] к {\displaystyle к} н > 0 {\displaystyle n>0} н {\displaystyle n} к {\displaystyle к}

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

Другая характеристика такова: Слово Линдона обладает тем свойством, что оно непустое, и всякий раз, когда оно разделено на две непустые подстроки, левая подстрока всегда лексикографически меньше правой подстроки. То есть, если — слово Линдона, а — любая факторизация на две подстроки, причем и подразумевается как непустые, то . Это определение подразумевает, что строка длины является словом Линдона тогда и только тогда, когда существуют слова Линдона и такие, что и . [4] Хотя может быть более одного выбора и с этим свойством, существует конкретный выбор, называемый стандартной факторизацией , в котором является максимально возможной длиной. [5] ж {\displaystyle w} ж = ты в {\displaystyle w=uv} ты {\displaystyle u} в {\displaystyle v} ты < в {\displaystyle u<v} ж {\displaystyle w} ≥ 2 {\displaystyle \geq 2} ты {\displaystyle u} в {\displaystyle v} ты < в {\displaystyle u<v} ж = ты в {\displaystyle w=uv} ты {\displaystyle u} в {\displaystyle v} в {\displaystyle 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 )

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

Поколение

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

  1. Повторите и сократите его до нового слова длиной ровно . ж {\displaystyle w} х {\displaystyle x} н {\displaystyle n}
  2. Если последний символ является последним символом в отсортированном алфавитном порядке, удалите его, получив более короткое слово. х {\displaystyle x}
  3. Заменить последний оставшийся символ на его последующий символ в отсортированном порядке алфавита. х {\displaystyle x}

Например, предположим, что мы сгенерировали двоичные слова Линдона длиной до 7, и мы сгенерировали до , тогда шаги таковы: ж = 00111 {\displaystyle w=00111}

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

Худшее время для генерации преемника слова этой процедурой составляет . Однако, если генерируемые слова хранятся в массиве длины , а построение из выполняется путем добавления символов в конец , а не путем создания новой копии , то среднее время для генерации преемника (предполагая, что каждое слово одинаково вероятно) является постоянным. Таким образом, последовательность всех слов Линдона длиной не более может быть сгенерирована за время, пропорциональное длине последовательности. [7] Постоянная доля слов в этой последовательности имеет длину точно , поэтому ту же процедуру можно использовать для эффективной генерации слов длины точно или слов, длина которых делится , путем отфильтровывания сгенерированных слов, которые не соответствуют этим критериям. ж {\displaystyle w} О ( н ) {\displaystyle O(n)} н {\displaystyle n} х {\displaystyle x} ж {\displaystyle w} ж {\displaystyle w} ж {\displaystyle w} ж {\displaystyle w} н {\displaystyle n} н {\displaystyle n} н {\displaystyle n} н {\displaystyle n}

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

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

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

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

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

Дюваль (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 ] к текущим собранным символам, мы получим слово Линдона. Но мы пока не можем добавить его в список результатов, потому что оно может быть просто частью большего слова Линдона. Таким образом, просто увеличиваем m и устанавливаем k в 0, чтобы следующий символ сравнивался с первым в строке.
    3. S [ k ] больше, чем S [ m ]: если мы добавим S [ m ] к текущим собранным символам, это не будет ни словом Линдона, ни возможным началом одного из них. Таким образом, добавьте первые m − k собранных символов в список результатов, удалите их из строки, установите m в 1 и k в 0, чтобы они указывали на второй и первый символ строки соответственно.
  4. Когда m > N , это по сути то же самое, что столкнуться со значением минус бесконечности, поэтому добавляем первые m − k собранных символов в список результатов после удаления их из строки, устанавливаем m равным 1, а k равным 0 и возвращаемся к предыдущему шагу.
  5. Добавьте S в список результатов.

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

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

0 0001 0011 01 0111 1

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

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

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

Для простого числа p число неприводимых мономических многочленов степени d над полем равно числу слов Линдона длины d в алфавите из p символов; их можно поставить в явное соответствие. [15] Ф п {\displaystyle \mathbb {F} _{p}}

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

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

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

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

Примечания

  1. ↑ Линдон (1954).
  2. ^ Ширшов (1953).
  3. ^ аб Берстель и Перрин (2007); Мелансон (2001).
  4. ^ abc Мелансон (2001).
  5. ^ Берстель и Перрин (2007).
  6. ^ Раски (2003) приводит подробную информацию об этих подсчетах для слов Линдона и нескольких связанных с ними понятий.
  7. ^ Берстель и Поччиола (1994).
  8. ^ Мелансон (2001). Берстель и Перрен (2007) пишут, что хотя это обычно приписывают Чену, Фоксу и Линдону (1958) и следует из результатов этой статьи, это не было заявлено явно до Шютценбергера (1965). Это было сформулировано явно Ширшовым (1958), см. Шютценбергера и Шермана (1963).
  9. ^ ab Duval (1983).
  10. ^ Гил и Скотт (2009); Куфлейтнер (2009).
  11. ^ Брлек и др. (2009).
  12. ^ Глен (2012).
  13. ^ Мелансон (1992); Мелансон и Ройтенауэр (1989); Хольвег и Ройтенауэр (2003)
  14. ^ По данным Берстеля и Перрена (2007), последовательность, сгенерированная таким образом, была впервые описана (с другим методом генерации) Мартином (1934), а связь между ней и словами Линдона была обнаружена Фредриксеном и Майораной (1978).
  15. ^ Голомб (1969).
  16. ^ ab Radford (1979)

Ссылки

  • Берстель, Жан; Перрен, Доминик (2007), «Истоки комбинаторики слов» (PDF) , Европейский журнал комбинаторики , 28 (3): 996–1022, doi : 10.1016/j.ejc.2005.07.019 , MR  2300777.
  • Берстель, Дж.; Поччиола, М. (1994), «Средняя стоимость алгоритма Дюваля для генерации слов Линдона» (PDF) , Теоретическая информатика , 132 (1–2): 415–425, doi : 10.1016/0304-3975(94)00013-1 , MR  1290554.
  • Брлек, С.; Лашо, Ж.-О.; Провансаль, X.; Ройтенауэр, К. (2009), «Линдон + Кристоффель = цифровая выпуклость» (PDF) , Распознавание образов , 42 (10): 2239–2246, Бибкод : 2009PatRe..42.2239B, doi : 10.1016/j.patcog.2008.11. 010.
  • Чен, К.-Т.; Фокс, Р.Х .; Линдон, Р.К. (1958), «Свободное дифференциальное исчисление. IV. Фактор-группы нижнего центрального ряда», Annals of Mathematics , 2-я серия, 68 (1): 81–95, doi :10.2307/1970044, JSTOR  1970044, MR  0102539.
  • Дюваль, Жан-Пьер (1983), «Разложение слов на множители в упорядоченном алфавите», Журнал алгоритмов , 4 (4): 363–381, doi :10.1016/0196-6774(83)90017-2.
  • Дюваль, Жан-Пьер (1988), «Génération d'unesection des classs de conjugaison et arbre des mots de Lindon de longueurbornée», Theoretical Computer Science (на французском языке), 60 (3): 255–283, doi : 10.1016 /0304-3975(88)90113-2, МР  0979464.
  • Фредриксен, Гарольд; Майорана, Джеймс (1978), «Ожерелья из бусин k цветов и k -арные последовательности де Брейна», Дискретная математика , 23 (3): 207–210, doi : 10.1016/0012-365X(78)90002-X , MR  0523071.
  • Гил, Дж.; Скотт, Д.А. (2009), Биективное преобразование сортировки строк (PDF).
  • Глен, Эми (2012), «Комбинаторика слов Линдона» (PDF) , Мини-конференция: Комбинаторика, представления и структура типа Ли , Мельбурнский университет
  • Голомб, Соломон В. (1969), «Неприводимые многочлены, синхронизирующие коды, примитивные ожерелья и циклотомическая алгебра», в Бозе, Р. К.; Доулинг, ТА (ред.), Комбинаторная математика и ее приложения: Труды конференции, состоявшейся в Университете Северной Каролины в Чапел-Хилл, 10–14 апреля 1967 г. , Серия монографий Университета Северной Каролины по теории вероятности и статистике, т. 4, Издательство Университета Северной Каролины, стр. 358–370, ISBN 9780807878200, OCLC  941682678
  • Хольвег, Кристоф; Ройтенауэр, Кристоф (2003), «Слова, перестановки и деревья Линдона» (PDF) , Теоретическая информатика , 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
  • Линдон, RC (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], "Lyndon word", Энциклопедия математики , EMS Press
  • Мелансон, Гай; Ройтенауэр, Кристоф (1989), «Слова Линдона, свободные алгебры и перетасовки», Канадский журнал математики , 41 (4): 577–591, doi : 10.4153/CJM-1989-025-2 , S2CID  17395250
  • Раски, Фрэнк (2003), Информация о ожерельях, слова Линдона, последовательности Де Брейна, архивировано из оригинала 2006-10-02.
  • Шютценбергер, М. П.; Шерман, С. (1963), «О формальном произведении над сопряженными классами в свободной группе», Журнал математического анализа и приложений , 7 (3): 482–488, doi : 10.1016/0022-247X(63)90070-2 , MR  0158002.
  • Шютценбергер, MP (1965), «О факторизации свободных моноидов», Труды Американского математического общества , 16 (1): 21–24, doi :10.2307/2033993, JSTOR  2033993, MR  0170971.
  • Ширшов, А.И. (1953), «Подалгебры свободных алгебр Ли», Матем. сборник , Новая серия, 33 (75): 441–452, MR  0059892
  • Ширшов, А.И. (1958), «О свободных кольцах Ли», Матем. сборник , Новая серия, 45 (87): 113–122, MR  0099356
  • Рэдфорд, Дэвид Э. (1979), «Естественный кольцевой базис для тасованной алгебры и его применение к групповым схемам», Журнал алгебры , 58 (2): 432–454, doi : 10.1016/0021-8693(79)90171-6.
Взято с "https://en.wikipedia.org/w/index.php?title=Lyndon_word&oldid=1239039631"