Линдон слово - 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».
Пустая строка также соответствует определению слова Линдона нулевой длины. Количество двоичных слов Линдона каждой длины, начиная с нулевой длины, образует целочисленную последовательность
Слова Линдона соответствуют представителям класса апериодических ожерелий и, таким образом, могут быть подсчитаны с помощью функции подсчета ожерелий Моро .
Поколение
Дюваль (1988) предлагает эффективный алгоритм для перечисления слов Линдона длины не более n с заданным размером алфавита s в лексикографическом порядке . Если w - одно из слов в последовательности, то следующее слово после w можно найти, выполнив следующие действия:
- Повторите символы из w, чтобы сформировать новое слово x длины точно n , где i- й символ x совпадает с символом в позиции ( i mod length ( w )) слова w .
- Пока последний символ x является последним символом в отсортированном порядке алфавита, удалите его, получив более короткое слово.
- Замените последний оставшийся символ x его преемником в отсортированном порядке алфавита.
Наихудшее время для создания преемника слова w с помощью этой процедуры составляет O ( n ). Однако, если генерируемые слова хранятся в массиве длины n , и построение x из w выполняется путем добавления символов в конец w, а не путем создания новой копии w , тогда среднее время генерации преемник w (при условии, что каждое слово одинаково вероятен) постоянен. Следовательно, последовательность всех слов Линдона длиной не больше n может быть сгенерирована за время, пропорциональное длине последовательности. Постоянная часть слов в этой последовательности имеет длину ровно n , поэтому ту же процедуру можно использовать для эффективного создания слов длины ровно n или слов, длина которых делит n , путем фильтрации сгенерированных слов, не соответствующих этим критериям.
Стандартная факторизация
Согласно теореме Чена – Фокса – Линдона , каждая строка может быть сформирована уникальным способом путем конкатенации последовательности слов Линдона таким образом, чтобы слова в последовательности не увеличивались лексикографически. Последнее слово Линдона в этой последовательности является лексикографически наименьшим суффиксом данной строки. Факторизация в невозрастающую последовательность слов Линдона (так называемая факторизация Линдона) может быть построена за линейное время . Факторизации Линдона можно использовать как часть биективного варианта преобразования Барроуза – Уиллера для сжатия данных , а также в алгоритмах цифровой геометрии .
Такие факторизации могут быть записаны (однозначно) как конечные бинарные деревья, листья которых помечены алфавитом, а каждая правая ветвь задается последним словом Линдона в последовательности. Такие деревья иногда называют стандартными скобками, и их можно рассматривать как факторизацию элементов свободной группы или как базисные элементы для свободной алгебры Ли . Эти деревья являются частным случаем деревьев Холла (поскольку слова Линдона являются частным случаем холловских слов), и, таким образом, слова Холла обеспечивают стандартный порядок, называемый процессом сбора коммутаторов для групп, и базисом для алгебр Ли. Действительно, они обеспечивают явную конструкцию коммутаторов, фигурирующих в теореме Пуанкаре – Биркгофа – Витта, необходимых для построения универсальных обертывающих алгебр .
Каждое слово Lyndon можно понимать как перестановку , стандартную перестановку суффиксов .
Алгоритм Дюваля
Дюваль (1983) разработал алгоритм для поиска стандартной факторизации, работающей в линейном времени и постоянном пространстве. Он перебирает строку, пытаясь найти как можно более длинное слово Линдона. Найдя его, он добавляет его в список результатов и переходит к поиску оставшейся части строки. Результирующий список строк является стандартной факторизацией данной строки. Далее следует более формальное описание алгоритма.
Для строки S длины N следует выполнить следующие шаги:
- Пусть m будет индексом символа-кандидата, который будет добавлен к уже собранным символам. Изначально m = 1 (индексы символов в строке начинаются с нуля).
- Пусть k будет индексом символа, с которым мы будем сравнивать другие. Первоначально k = 0 .
- Пока k и m меньше N , сравните S [k] ( k -й символ строки S ) с S [m] . Возможны три исхода:
- S [k] равно S [m] : добавить S [m] к текущим собранным символам. Увеличиваем k и m .
- S [k] меньше S [m] : если мы добавим S [m] к текущим собранным символам, мы получим слово Линдона. Но мы пока не можем добавить его в список результатов, потому что это может быть просто частью большего слова Lyndon. Таким образом, просто увеличьте m и установите k равным 0, чтобы следующий символ сравнивался с первым в строке.
- S [k] больше, чем S [m] : если мы добавим S [m] к текущим набранным символам, это не будет ни словом Линдона, ни возможным его началом. Таким образом, добавьте первые mk собранных символов в список результатов, удалите их из строки, установите m в 1 и k в 0, чтобы они указывали на второй и первый символы строки соответственно.
- Когда m> N , это практически то же самое, что встреча с минус бесконечностью, поэтому добавьте первые mk собранных символов в список результатов после удаления их из строки, установите m на 1 и k на 0 и вернитесь к предыдущему шагу.
- Добавьте 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 с неопределенными, соответствующими словам Линдона.
Смотрите также
- Лексикографически минимальное вращение струны
- Морфическое слово
- Штурмское слово
- Ожерелье (комбинаторика)
Примечания
использованная литература
- Берстель, Жан; Перрин, Доминик (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.
- 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..
- Шютценбергер, депутат; Шерман, 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.