Słowo Lyndona

W matematyce , kombinatoryce i informatyce słowo Lyndona to niepusty ciąg znaków , który w porządku leksykograficznym jest znacznie mniejszy niż wszystkie jego obroty . Słowa Lyndona zostały nazwane na cześć matematyka Rogera Lyndona , który zbadał je w 1954 roku, nazywając je standardowymi sekwencjami leksykograficznymi . Anatolij Szirszow wprowadził słowa Lyndona w 1953 roku, nazywając je zwykłymi słowami . Słowa Lyndona są szczególnym przypadkiem słów Halla ; prawie wszystkie właściwości słów Lyndona są wspólne dla słów Halla.

Definicje

Istnieje kilka równoważnych definicji.

A ${\ displaystyle k}$ -ary słowo Lyndona o długości ${\ displaystyle n> 0}$ $to$ ciąg nad alfabetem o rozmiarze $k}$ który jest unikalnym k {\ displaystyle minimalny element porządku leksykograficznego w multizbiorze wszystkich jego obrotów. Bycie wyjątkowo najmniejszą rotacją oznacza, że słowo Lyndona różni się od którejkolwiek z jego nietrywialnych rotacji, a zatem jest aperiodyczne.

Alternatywnie, słowo $,$ ${\ displaystyle w$ gdy jest niepuste i leksykograficznie ściśle mniejsze niż którykolwiek z jego właściwych przyrostków, to znaczy dla wszystkich niepustych słów $displaystyle v}$ $}$ $displaystyle u} nie$ takie, że $i$ \ puste

Inna charakterystyka jest następująca: Słowo Lyndona ma tę właściwość, że jest niepuste i zawsze, gdy jest dzielone na dwa niepuste podłańcuchy, lewy podłańcuch jest zawsze leksykograficznie mniejszy niż prawy podłańcuch. To znaczy, jeśli $i$ słowem Lyndona i $u}$ $displaystyle$ rozkładem na czynniki na dwa podłańcuchy, z rozumianym v $v}$ być niepusty, to ${\ displaystyle u <v}$ . Ta definicja implikuje $,$ że ciąg $długości jest słowem Lyndona$ gdy istnieją słowa Lyndona takie, że u $\ displaystyle u}$ i ${\ displaystyle v}$ ${\ displaystyle u <v}$ i ${\ displaystyle w = uv}$ . Chociaż może być więcej niż $jeden$ i $właściwością$ istnieje szczególny wybór, zwany $standardową$ faktoryzacją , w której jest długo, jak to możliwe.

Wyliczenie

Słowa Lyndona nad dwusymbolowym alfabetem binarnym {0,1}, posortowane według długości, a następnie leksykograficznie w każdej klasie długości, tworzą nieskończoną sekwencję, która zaczyna się

0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...

Pierwszy ciąg, który nie należy do tego ciągu, „00”, jest pomijany, ponieważ jest okresowy (składa się z dwóch powtórzeń podłańcucha „0”); drugi pominięty ciąg, „10”, jest aperiodyczny, ale nie jest minimalny w swojej klasie permutacji, ponieważ może być cyklicznie permutowany do mniejszego ciągu „01”.

Pusty ciąg spełnia również definicję słowa Lyndona o długości zero. Liczby binarnych słów Lyndona o każdej długości, począwszy od długości zero, tworzą sekwencję całkowitą

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (sekwencja A001037 w OEIS )

Słowa Lyndona odpowiadają aperiodycznym przedstawicielom klas naszyjników i dlatego można je policzyć za pomocą funkcji liczenia naszyjników Moreau .

Pokolenie

$($ 1988) zapewnia wydajny algorytm wymieniania słów Lyndona o długości co najwyżej $danym$ rozmiarem alfabetu porządku leksykograficznym . Jeśli $w$ jednym ze słów w sekwencji, to następne słowo po można znaleźć, wykonując następujące czynności: $\ displaystyle w}$

$x$ symbole z $.$ aby utworzyć nowe słowo o długości dokładnie $}$ gdzie $symbolem$ jest x $\$ tak samo jak symbol na pozycji $}$ length ( ${\ displaystyle w}$ ) ${\ displaystyle w$ .
Dopóki ostatni symbol $posortowanej$ kolejności alfabetu, usuń go, tworząc krótsze słowo.
Zastąp ostatni pozostały symbol $następcą$ w posortowanej kolejności alfabetu.

W najgorszym przypadku czas na wygenerowanie następnika słowa $displaystyle$ pomocą tej procedury to $O (n)}$ . Jeśli jednak generowane słowa są przechowywane w $}$ $o$ długości $dodanie$ a konstrukcja z $x$ przez symboli na końcu $displaystyle w}$ zamiast tworzenia nowej kopii ${\ displaystyle w}$ , to średni czas wygenerowania następnika $)$ jest stały. Dlatego sekwencja wszystkich długości słów Lyndona $czasie$ proporcjonalnym do długości sekwencji. Stały ułamek słów w tej sekwencji ma długość dokładnie $,$ ta sama procedura może być użyta do wydajnego generowania słów o długości dokładnie ${\ displaystyle n}$ słów, których długość dzieli ${\ displaystyle n}$ , odfiltrowując wygenerowane słowa, które nie spełniają tych kryteriów.

Standardowa faktoryzacja

Zgodnie z twierdzeniem Chen-Fox-Lyndon , każdy ciąg może być utworzony w unikalny sposób przez połączenie sekwencji słów Lyndona, w taki sposób, że słowa w sekwencji nie rosną leksykograficznie. Ostatnim słowem Lyndona w tej sekwencji jest leksykograficznie najmniejszy sufiks podanego ciągu. Faktoryzacja na nierosnący ciąg słów Lyndona (tzw. faktoryzacja Lyndona) może być skonstruowana w czasie liniowym . Rozkłady na czynniki Lyndona mogą być używane jako część bijektywnego wariantu transformaty Burrowsa-Wheelera do kompresji danych oraz w algorytmach do geometria cyfrowa .

Takie rozkłady na czynniki można zapisać (jedynie) jako skończone drzewa binarne, z liśćmi oznaczonymi alfabetem, z każdą prawą gałęzią określoną przez ostatnie słowo Lyndona w sekwencji. Takie drzewa są czasami nazywane standardowymi nawiasami i mogą być traktowane jako faktoryzacja elementów wolnej grupy lub jako elementy podstawowe dla wolnej algebry Liego . Drzewa te są szczególnym przypadkiem drzew Halla (ponieważ słowa Lyndona są szczególnym przypadkiem słów Halla), podobnie słowa Halla zapewniają standardową kolejność, zwaną procesem zbierania komutatora dla grup i podstawy dla algebr Liego. Rzeczywiście, zapewniają one wyraźną konstrukcję komutatorów występujących w twierdzeniu Poincarégo – Birkhoffa – Witta, potrzebnych do konstrukcji uniwersalnych algebr obejmujących .

Każde słowo Lyndona może być rozumiane jako permutacja , standardowa permutacja sufiksu .

Algorytm Duvala

Duval (1983) opracował algorytm znajdowania standardowego rozkładu na czynniki, który działa w czasie liniowym i stałej przestrzeni. Iteruje po łańcuchu, próbując znaleźć jak najdłuższe słowo Lyndona. Kiedy go znajdzie, dodaje go do listy wyników i przechodzi do wyszukiwania pozostałej części ciągu. Wynikowa lista ciągów jest standardową faktoryzacją danego ciągu. Poniżej znajduje się bardziej formalny opis algorytmu.

Biorąc pod uwagę łańcuch S o długości N , należy wykonać następujące kroki:

Niech m będzie indeksem kandydata na symbol, który ma zostać dołączony do już zebranych symboli. Początkowo m = 1 (indeksy symboli w łańcuchu zaczynają się od zera).
Niech k będzie indeksem symbolu, do którego porównalibyśmy inne. Początkowo k = 0 .
Podczas gdy k i m są mniejsze niż N , porównaj S[k] ( k -ty symbol łańcucha S ) z S[m] . Możliwe są trzy wyniki:
1. S[k] jest równe S[m] : dołącz S[m] do aktualnie zebranych symboli. Przyrost k i m .
2. S[k] jest mniejsze niż S[m] : jeśli dodamy S[m] do aktualnie zebranych symboli, otrzymamy słowo Lyndona. Ale nie możemy jeszcze dodać go do listy wyników, ponieważ może to być tylko część większego słowa Lyndon. Zatem po prostu zwiększ m i ustaw k na 0, aby następny symbol został porównany z pierwszym w łańcuchu.
3. S[k] jest większe niż S[m] : jeśli dołączymy S[m] do aktualnie zebranych symboli, nie będzie to ani słowo Lyndona, ani możliwy początek jednego. W ten sposób dodaj pierwsze mk do listy wyników, usuń je z łańcucha, ustaw m na 1 i k na 0, tak aby wskazywały odpowiednio na drugi i pierwszy symbol ciągu.
Kiedy m > N , jest to zasadniczo to samo, co napotkanie minus nieskończoności, dlatego dodaj pierwsze zebrane symbole mk do listy wyników po usunięciu ich z łańcucha, ustaw m na 1 i k na 0 i wróć do poprzedniego kroku.
Dodaj S do listy wyników.

Połączenie z sekwencjami de Bruijna

Jeśli połączymy ze sobą, w porządku leksykograficznym, wszystkie słowa Lyndona, których długość dzieli daną liczbę n , otrzymamy sekwencję de Bruijna , cykliczną sekwencję symboli, w której każda możliwa sekwencja długości- n pojawia się dokładnie raz jako jedna z jej ciągłe podciągi. Na przykład konkatenacja binarnych słów Lyndona, których długość dzieli cztery, to

0 0001 0011 01 0111 1

Ta konstrukcja, wraz z wydajnym generowaniem słów Lyndona, zapewnia wydajną metodę konstruowania określonej sekwencji de Bruijna w czasie liniowym i przestrzeni logarytmicznej .

Dodatkowe właściwości i zastosowania

Słowa Lyndona mają zastosowanie do opisu algebr Liego swobodnego , przy konstruowaniu bazy części jednorodnej danego stopnia; to była pierwotna motywacja Lyndona do wprowadzenia tych słów. Słowa Lyndona można rozumieć jako szczególny przypadek zbiorów Halla .

Dla liczby pierwszej p liczba nieredukowalnych wielomianów monicznych stopnia d nad polem jest taka sama, jak liczba słów Lyndona o długości d w alfabecie p symboli; fa ${f} _ {p}}$ można je umieścić w wyraźnej korespondencji.

Twierdzenie Radforda stwierdza, że algebrę tasowania na polu o charakterystyce 0 można postrzegać jako algebrę wielomianową na słowach Lyndona. Dokładniej, niech A będzie alfabetem, niech k będzie polem o charakterystyce 0 (lub, bardziej ogólnie, przemienną -algebrą ⟨ x _a | za ∈ ZA ⟩ ) i niech R będzie swobodną nieprzemienną k $.$ k . Słowa nad A można wtedy utożsamiać z „nieprzemiennymi jednomianami” (tj. iloczynami x _a ) w R ; mianowicie utożsamiamy słowo ( a ₁ , a ₂ ,..., an ) _. z jednomianem x _{a ₁} x _{a ₂} ... x _{a _n} Zatem słowa nad A tworzą bazę przestrzeni k -wektorowej R . Następnie produkt losowy jest definiowany na R ; jest to k -bililiniowy, asocjacyjny i przemienny, który jest oznaczony przez ш i który na słowach może być rekurencyjnie zdefiniowany przez

1 ш v = v dla dowolnego słowa v ;

u ш 1 = u dla dowolnego słowa u ;

ua ш vb = ( u ш vb ) za + ( ua ш v ) b dla dowolnego a , b ∈ A i dowolnych słów u i v .

Algebra tasowania w alfabecie A jest zdefiniowana jako grupa addytywna R obdarzona ш jako mnożenie. Twierdzenie Radforda stwierdza teraz, że słowa Lyndona są algebraicznie niezależnymi elementami tej algebry tasowania i generują ją; tak więc algebra tasowania jest izomorficzna z pierścieniem wielomianowym nad k , przy czym nieokreśloności odpowiadają słowom Lyndona.

Zobacz też

Notatki

Berstel, Jean; Perrin, Dominique (2007), „Początki kombinatoryki na słowach” (PDF) , European Journal of Combinatorics , 28 (3): 996–1022, doi : 10.1016/j.ejc.2005.07.019 , MR 2300777 .
Berstel, J.; Pocchiola, M. (1994), „Średni koszt algorytmu Duvala do generowania słów Lyndona” (PDF) , Theoretical Computer Science , 132 (1–2): 415–425, doi : 10.1016 / 0304-3975 (94) 00013- 1 , MR 1290554 .
Brlek S.; Lachaud, J.-O.; Prowansalski, X .; Reutenauer, C. (2009), „Lyndon + Christoffel = cyfrowo wypukły” (PDF) , Rozpoznawanie wzorców , 42 (10): 2239–2246, doi : 10.1016/j.patcog.2008.11.010 .
Chen, KT; Fox, RH ; Lyndon, RC (1958), „Rachunek różniczkowy swobodny. IV. Grupy ilorazowe dolnego szeregu środkowego”, Annals of Mathematics , 2 Ser., 68 (1): 81–95, doi : 10,2307/1970044 , JSTOR 1970044 , MR 0102539 .
Duval, Jean-Pierre (1983), „Rozkład słów na czynniki w uporządkowanym alfabecie”, Journal of Algorithms , 4 (4): 363–381, doi : 10.1016/0196-6774 (83) 90017-2 .
Duval , Jean - Pierre ( 1988 ) /0304-3975(88)90113-2 , MR 0979464 .
Fredricksen, Harold; Maiorana, James (1978), „Naszyjniki z koralików w k kolorach i sekwencjach k -ary de Bruijn”, Discrete Mathematics , 23 (3): 207–210, doi : 10.1016 / 0012-365X (78) 90002-X , MR 0523071 .
Gil, J.; Scott, DA (2009), Bijective string sorting transform (PDF) .
Glen, Amy (2012), „Kombinatoryka słów Lyndona” (PDF) , Mini-konferencja: Kombinatoryka, reprezentacje i struktura typu Lie , University of Melbourne
Golomb, Solomon W. (1969), „Nieredukowalne wielomiany, kody synchronizujące, prymitywne naszyjniki i algebra cyklotomiczna”, w: Bose, RC; Dowling, TA (red.), Kombinatoryczna matematyka i jej zastosowania: Materiały z konferencji, która odbyła się na Uniwersytecie Karoliny Północnej w Chapel Hill, 10-14 kwietnia 1967 r. , Seria monografii Uniwersytetu Karoliny Północnej w zakresie prawdopodobieństwa i statystyki, tom. 4, University of North Carolina Press, s. 358–370, ISBN 9780807878200 , OCLC 941682678
Hohlweg, Christophe; Reutenauer , Christophe ( 2003 ) _ _ _ _ _ _
Kufleitner, Manfred (2009), „O bijektywnych wariantach transformacji Burrowsa-Wheelera ”, w: Holub, Jan; Žďárek, Jan (red.), Praska konferencja strunologiczna , s. 65–69, arXiv : 0908.0239 , Bibcode : 2009arXiv0908.0239K .
Lothaire, M. (1983), Kombinatoryka słów , Encyklopedia matematyki i jej zastosowań, tom. 17, Addison-Wesley Publishing Co., Reading, Massachusetts, ISBN 978-0-201-13516-9 , MR 0675953
Lyndon, RC (1954), „O problemie Burnside'a”, Transactions of the American Mathematical Society , 77 (2): 202–215, doi : 10.2307/1990868 , JSTOR 1990868 , MR 0064049 .
Martin, MH (1934), „Problem w układach”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , 40 (12): 859–864, doi : 10.1090/S0002-9904-1934-05988-3 , MR 1562989 .
Melançon, Guy (1992), „Kombinatoryka drzew Hall i słów Hall” (PDF) , Journal of Combinatorial Theory , Seria A, 59 (2): 285–308, doi : 10.1016 / 0097-3165 (92) 90070-B
Melançon, G. (2001) [1994], „Słowo Lyndona” , Encyklopedia matematyki , EMS Press
Melançon, Guy; Reutenauer, Christophe (1989), „Słowa Lyndona, wolne algebry i przetasowania”, Canadian Journal of Mathematics , 41 (4): 577–591, doi : 10.4153 / CJM-1989-025-2 , S2CID 17395250
Ruskey, Frank (2003), Informacje o naszyjnikach, słowa Lyndona, sekwencje De Bruijn , zarchiwizowane od oryginału w dniu 2006-10-02 .
Schützenberger, poseł ; Sherman, S (1963), „O iloczynie formalnym nad klasami sprzężonymi w wolnej grupie”, Journal of Mathematical Analysis and Applications , 7 (3): 482–488, doi : 10.1016 / 0022-247X (63) 90070- 2 , MR 0158002 .
Schützenberger, MP (1965), „O faktoryzacji wolnych monoidów”, Proceedings of the American Mathematical Society , 16 (1): 21–24, doi : 10.2307/2033993 , JSTOR 2033993 , MR 0170971 .
Shirshov, AI (1953), „Podalgebry swobodnych algebr Liego”, Mat. Sbornik , Nowa seria, 33 (75): 441–452, MR 0059892
Shirshov, AI (1958), „O wolnych pierścieniach kłamstwa”, Mat. Sbornik , Nowa seria, 45 (87): 113–122, MR 0099356
Radford, David E. (1979), „Podstawa naturalnego pierścienia dla algebry tasowania i zastosowanie do schematów grupowych”, Journal of Algebra , 58 (2): 432–454, doi : 10.1016 / 0021-8693 (79) 90171 -6 .