Słowo Lyndona

Słowo Lyndona lub słowo pierwsze – niepuste słowo spełniające dwa warunki:

• jest pierwotne, tzn. nie można go przedstawić w postaci potęgi $u^{k}$ dla $k\geqslant 2$,
• wśród swoich cyklicznych obrotów jest najmniejsze względem porządku leksykograficznego $\preccurlyeq .$

Przykładowo dla alfabetu $\{a,b\}$ można utworzyć 8 słów Lyndona nie dłuższych niż 4 litery ułożonych w porządku leksykograficznym:

$a,\ aaab,\ aab,\ aabb,\ ab,\ abb,\ abbb,\ b$.

Twierdzenia

Twierdzenie 1

Słowo jest słowem Lyndona wtedy i tylko wtedy, gdy jest niepuste i jest wcześniejsze w porządku leksykograficznym niż każdy jego sufiks właściwy.

Twierdzenie 2

Słowo jest słowem Lyndona wtedy i tylko wtedy, gdy jest słowem jednoliterowym lub da się przedstawić jako złożenie dwóch słów Lyndona, w którym pierwsze słowo jest wcześniejsze w porządku leksykograficznym niż drugie.

Powyższe dwa twierdzenia pozwalają sformułować dwie nowe definicje słowa Lyndona równoważne definicji ze wstępu.

Twierdzenie 3

Dowolne słowo można podzielić na słowa Lyndona $s=l_{1}l_{2}\dots l_{k},$ a rozkład ten jest jednoznaczny jeśli spełnia warunek monotoniczności $l_{k}\preccurlyeq \dots \preccurlyeq l_{2}\preccurlyeq l_{1}$ . W literaturze wynik takiego podziału jest nazywany rozkładem Lyndona (ang. Lyndon factorization) lub rozkładem standardowym (ang. standard factorization).

Twierdzenie 4

Rozkład Lyndona można wyznaczyć w czasie liniowym .

Historia

Nazwa słowa pochodzi od amerykańskiego matematyka Rogera Lyndona, który je opisał w 1954 wskazując, że są to „standardowe” leksykograficznie ciągi. Zostały one również zdefiniowane w 1953 przez rosyjskiego matematyka Anatolija Szyrszowa jako poprawne słowa (ros. правильные слова).

Efektywny algorytm na dzielenie słów na słowa Lyndona opublikował Jean-Pierre Duval w 1983 , który działał w liniowym czasie i przy stałym zapotrzebowaniu na pamięć. W kolejnych latach powstawały następne wersje na przykład działające równolegle, korzystające z zewnętrznej pamięci lub obsługujące dane skompresowane.

Jean-Pierre Duval opublikował w 1988 również algorytm na generowanie słów Lyndona dla podanego alfabetu i rozmiaru słów .

Zastosowanie

Słowa Lyndona są wynikiem zdefiniowania elementów bazy w wolnej algebrze Liego.

W kolejnych latach znalazły zastosowanie w algorytmach tekstowych stosowanych w informatyce i bioinformatyce, a zwłaszcza w sortowaniu i analizie sekwencji DNA. Znalazły one również zastosowanie w generowaniu ciągów de Bruijna.

Zobacz też

• obrót bitowy
• transformata Burrowsa-Wheelera

Bibliografia

• FrédériqueF. Bassino FrédériqueF., JulienJ. Clément JulienJ., CyrilC. Nicaud CyrilC., The standard factorization of Lyndon words: an average point of view, „Discrete Mathematics”, 290 (1), 2005, s. 1–25, DOI: 10.1016/j.disc.2004.11.002  (ang.).
• K.T.K.T. Chen K.T.K.T., R.H.R.H. Fox R.H.R.H., R.C.R.C. Lyndon R.C.R.C., Free differential calculus, IV. The quotient groups of the lower central series, „Annals of Mathematics”, 68 (1), 1958, s. 81–95, DOI: 10.2307/1970044, JSTOR: 1970044  (ang.).
• Jean-PierreJ.P. Duval Jean-PierreJ.P., Factorizing words over an ordered alphabet, „Journal of Algorithms”, 4 (4), 1983, s. 263–281, DOI: 10.1016/0196-6774(83)90017-2  (ang.).
• Jean-PierreJ.P. Duval Jean-PierreJ.P., Génération d’une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée, „Theoretical Computer Science”, 60, 1988, s. 255–283, DOI: 10.1016/0012-365X(78)90002-X  (fr.).
• Sukhpal SinghS.S. Ghuman Sukhpal SinghS.S., EmanueleE. Giaquinta EmanueleE., JormaJ. Tarhio JormaJ., Alternative Algorithms for Lyndon Factorization, „arXiv.org”, 2014, arXiv:1405.4892  (ang.).
• ŁukaszŁ. Grządko ŁukaszŁ., O rozkładzie słów na słowa Lyndona, „Delta”, styczeń 2015 [dostęp 2018-06-27] .
• JacekJ. Jagodziński JacekJ., Metody planowania ruchu układów bezdryfowych bazujące na algorytmie Lafferriera-Sussmanna, Praca doktorska, Wrocław 2011 [zarchiwizowane 2018-01-30] .
• R.C.R.C. Lyndon R.C.R.C., On Burnside’s Problem, „Transactions of the American Mathematical Society”, 77 (2), 1954, s. 202–215, DOI: 10.2307/1990868, JSTOR: 1990868  (ang.).
• SabrinaS. Mantaci SabrinaS. i inni, Sorting suffixes of a text via its Lyndon Factorization, „Proceedings of the Prague Stringology Conference”, 2013, arXiv:1306.1366 .
• JakubJ. Radoszewski JakubJ., Generowanie minimalnych leksykograficznie ciągów de Bruijna za pomocą słów Lyndona [online], Uniwersytet Warszawski, wrzesień 2008 .
• JakubJ. Radoszewski JakubJ., Słowa pierwsze, „Delta”, grudzień 2010, s. 3–4 [dostęp 2018-06-27] .
• A.I.A.I. Shirshov A.I.A.I., Subalgebras of Free Lie Algebras, M.R.M.R. Bremner (tłum.), M.V.M.V. Kochetov (tłum.), Springer, 2009  (ang.).
• Анатолий ИлларионовичА.И. Ширшов Анатолий ИлларионовичА.И., Подалгебры свободных лиевых алгебр, „Матем. сб.”, 33 (2), 1953, s. 441–452  (ros.).

Linki zewnętrzne

• AmyA. Glen AmyA., Combinatorics of Lyndon words, Murdoch University, 16 lutego 2012  (ang.).brak strony (książka)
• TomaszT. Kociumaka TomaszT., JakubJ. Radoszewski JakubJ., WojciechW. Rytter WojciechW., Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence, „Combinatorial Pattern Matching”, 2014, s. 202–211, DOI: 10.1007/978-3-319-07566-2_21  (ang.).
• ArturoA. Carpi ArturoA. i inni, Universal Lyndon Words, „Lecture Notes in Computer Science” (8634), 2014, s. 135–146, DOI: 10.1007/978-3-662-44522-8_12, arXiv:1406.5895  (ang.).
• GuyG. Melançon GuyG., ChristopheCh. Reutenauer ChristopheCh., Lyndon words, free algebras and shuffles, „Can. J. Math.”, XLI (4), 1989, s. 577–591, DOI: 10.4153/CJM-1989-025-2  (ang.).