Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Определения [ править ]

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

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

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

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

Стандартная факторизация [ править ]

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

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

Каждое слово 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

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

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

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

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

Теорема Рэдфорда утверждает, что тасовая алгебра над полем характеристики 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 наделена ш в качестве умножения. Теорема Рэдфорда [18] теперь утверждает, что слова Линдона являются алгебраически независимыми элементами этой тасовой алгебры и порождают ее; таким образом, алгебра тасования изоморфна кольцу многочленов над k с неопределенными, соответствующими словам Линдона. [18]

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Линдон (1954) .
  2. ↑ Ширшов (1953) .
  3. ^ a b Berstel & Perrin (2007) ; Мелансон (2001) .
  4. ^ a b c Мелансон (2001) .
  5. ^ Berstel & Perrin (2007) .
  6. ^ Ruskey (2003) предоставляет подробные сведения об этих подсчетах слов Линдона и некоторых связанных с ними концепциях.
  7. ^ Berstel & Pocchiola (1994) .
  8. ^ Melancon (2001) . Berstel и Perrin (2007) пишут, что, хотя это обычно приписывается Чену, Фоксу и Линдону (1958) и следует из результатов этой статьи, это не было заявлено явно до Schützenberger (1965) . Он был явно сформулирован Ширшовым (1958) , см. Schützenberger & Sherman (1963) .
  9. ^ а б Дюваль (1983) .
  10. ^ Гил и Скотт (2009) ; Куфлейтнер (2009) .
  11. ^ Brlek et al. (2009) .
  12. ↑ Эми Глен, « Комбинаторика слов Линдона » (2012)
  13. ^ Гай Мелансон, (1992) " Комбинаторика деревьев Холла и слов Холла ", Журнал комбинаторной теории , 59A (2), стр. 285–308.
  14. ^ Guy Melancon и Кристоф Reutenauer (1989), "Линдон слова, свободные алгебры и перемешивает", Canadian Journal математики . 41 , No. 4, pp. 577-591.
  15. ^ Christophe Hohlweg и Christophe Reutenauer, " Lyndon слова, перестановки и деревья ", (2003) LaCIM
  16. ^ Согласно Berstel & Perrin (2007) , последовательность, сгенерированная таким образом, была впервые описана (с другим методом генерации) Мартином (1934) , а связь между ней и словами Линдона была обнаружена Fredricksen & Maiorana (1978) .
  17. ^ Соломон В. Голомб (1969) "Неприводимые многочлены, синхронизирующие коды, примитивные ожерелья и круговая алгебра", Proc. Conf Комбинаторная математика и ее приложения , стр. 358-370 (Университет Северной Каролины).
  18. ^ а б Рэдфорд (1979)

Ссылки [ править ]

  • Берстель, Жан; Перрин, Доминик (2007), "Истоки комбинаторики на словах" (PDF) , Европейский журнал комбинаторике , 28 (3): 996-1022, DOI : 10.1016 / j.ejc.2005.07.019 , MR  2300777.
  • Berstel, J .; Pocchiola, M. (1994), "Средняя стоимость алгоритма Дюваля для генерации Линдон слова" (PDF) , теоретическая информатика , 132 (1-2): 415-425, DOI : 10,1016 / 0304-3975 (94) 00013- 1 , Руководство по ремонту  1290554.
  • Brlek, S .; Lachaud, J.-O .; Провансальский, X .; Reutenauer, C. (2009), "Линдон + Кристоффел = цифровом выпуклым" (PDF) , Pattern Recognition , 42 (10): 2239-2246, DOI : 10.1016 / j.patcog.2008.11.010.
  • Chen, K.-T .; Fox, RH ; Линдон, RC (1958), "Свободное дифференциальное исчисление IV Факторпространства группы нижнего центрального ряда..", Annals математики , 2 - Ser,. 68 (1): 81-95, DOI : 10,2307 / 1970044 , JSTOR  1970044 , Руководство по ремонту  0102539.
  • Дюваль, Жан-Пьер (1983), «Факторизация слов по упорядоченному алфавиту», Журнал алгоритмов , 4 (4): 363–381, DOI : 10.1016 / 0196-6774 (83) 90017-2.
  • Duval, Жан-Пьер (1988), "Génération сГип раздел деза классы де conjugaison и др Арбры де словечки де Линдон де Longueur bornée", Теоретическая информатика (на французском языке), 60 (3): 255-283, DOI : 10.1016 / 0304-3975 (88) 90113-2 , MR  0979464.
  • Фредриксен, Гарольд; Maiorana, Джеймс (1978), "Колье из бисера в K цветах и к -ичной де Брейна последовательности", дискретная математика , 23 (3): 207-210, DOI : 10.1016 / 0012-365X (78) 90002-X , М.Р.  0523071.
  • Gil, J .; Скотт, Д.А. (2009 г.), Преобразование сортировки двухъективных строк (PDF).
  • Куфлейтнер, Манфред (2009), «О биективных вариантах преобразования Барроуза-Уиллера », в Holub, Jan; Жарек Ян (ред.), Пражская конференция по струнологии , стр. 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 CS1 maint: discouraged parameter (link).
  • Martin, MH (1934), "Проблема в аранжировках", Бюллетень Американского математического общества , 40 (12): 859-864, DOI : 10,1090 / S0002-9904-1934-05988-3 , MR  1562989.
  • Мелансон, Г. (2001) [1994], «Слово Линдона» , Энциклопедия математики , EMS Press
  • Раски, Фрэнк (2003), Информация об ожерельях, слова Линдона, последовательности Де Брёйна , заархивировано из оригинала 02.10.2006. CS1 maint: discouraged parameter (link).
  • Шютценбергер, депутат; Шерман, S (1963), "О формальном произведении над сопряженными классами в свободной группе", J. Math. Анальный. Прил. , 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, MR  0059892
  • Ширшов А.И. О свободных кольцах Ли (1958), Матем. Сборник , Новая серия, 45 (87): 113–122, MR  0099356
  • Рэдфорд, David E. (1979), "Естественное кольцо основа для воспроизведения в случайном порядке алгебры и приложение к групповым схемам", журнал алгебра , 58 (2): 432-454, DOI : 10,1016 / 0021-8693 (79) 90171 -6.