Tekst źródłowy strony Słowo Lyndona

'''Słowo Lyndona''' lub '''słowo pierwsze''' – niepuste [[słowo (matematyka)|słowo]] spełniające dwa warunki{{odn|Radoszewski|2010|s=4}}:
* jest ''pierwotne'', tzn. nie można go przedstawić w postaci potęgi <math>u^k</math> dla <math>k \geqslant 2</math><ref name="potęga" group="uwaga" />,
* wśród swoich cyklicznych obrotów<ref name="obrót cykliczny" group="uwaga" /> jest najmniejsze względem [[Porządek leksykograficzny|porządku leksykograficznego]] <math>\preccurlyeq.</math>

Przykładowo dla alfabetu <math>\{a,b\}</math> można utworzyć 8 słów Lyndona nie dłuższych niż 4 litery ułożonych w porządku leksykograficznym:
: <math>a,\ aaab,\ aab,\ aabb,\ ab,\ abb,\ abbb,\ b</math>{{odn|Duval|1988|s=271}}.

== Twierdzenia ==
; Twierdzenie 1 : Słowo jest słowem Lyndona wtedy i tylko wtedy, gdy jest niepuste i jest wcześniejsze w [[Porządek leksykograficzny|porządku leksykograficznym]] niż każdy jego [[Podsłowo#Sufiks|sufiks właściwy]]{{odn|Radoszewski|2010|s=4}}.
; 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{{odn|Radoszewski|2010|s=4}}.
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 <math>s = l_1 l_2 \dots l_k,</math> a rozkład ten jest jednoznaczny jeśli spełnia warunek monotoniczności <math>l_k \preccurlyeq \dots \preccurlyeq l_2 \preccurlyeq l_1</math>{{odn|Radoszewski|2010|s=4}}{{odn|Chen|Fox|Lyndon|1958}}{{odn|Grządko|2015|s=9}}. W literaturze wynik takiego podziału jest nazywany ''rozkładem Lyndona'' ({{ang.|Lyndon factorization}}){{odn|Mantaci|Restivol|Rosone|Sciortino|2013|s=2}} lub ''rozkładem standardowym'' (ang. {{k|en|standard factorization}}){{odn|Bassino|Clément|Nicaud|2005|s=3}}.
; Twierdzenie 4 : Rozkład Lyndona można wyznaczyć w [[Asymptotyczne tempo wzrostu|czasie liniowym]]{{odn|Duval|1983}}.

== Historia ==
{{Wikisłownik|standard|правильный}}
Nazwa słowa pochodzi od amerykańskiego matematyka {{link-interwiki|Roger Lyndon|tekst=Rogera Lyndona|Q=Q3439226}}, który je opisał w 1954 wskazując, że są to „standardowe” leksykograficznie ciągi{{odn|Lyndon|1954|s=203}}{{odn|Bassino|Clément|Nicaud|2005|s=1}}. Zostały one również zdefiniowane w 1953 przez rosyjskiego matematyka {{link-interwiki|Anatolij Szyrszow|tekst=Anatolija Szyrszowa|Q=Q4524490}} jako ''poprawne słowa'' ({{w języku|ru|правильные слова}}){{odn|Ширшов|1953|s=441–442}}{{odn|Shirshov|2009|s=66}}.

Efektywny algorytm na dzielenie słów na słowa Lyndona opublikował Jean-Pierre Duval w 1983{{odn|Grządko|2015|s=9}}{{odn|Duval|1983}}, który działał w [[Asymptotyczne tempo wzrostu|liniowym czasie]] i przy stałym zapotrzebowaniu na pamięć{{odn|Ghuman|Giaquinta|Tarhio|2014|s=1}}. 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{{odn|Ghuman|Giaquinta|Tarhio|2014|s=2}}.

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

== Zastosowanie ==
Słowa Lyndona są wynikiem zdefiniowania elementów bazy w {{link-interwiki|Wolna algebra Liego|tekst=wolnej algebrze Liego|Q=Q5499906}}{{odn|Jagodziński|2011|s=12}}.

W kolejnych latach znalazły zastosowanie w algorytmach tekstowych stosowanych w informatyce i bioinformatyce, a zwłaszcza w sortowaniu{{odn|Mantaci|Restivol|Rosone|Sciortino|2013|s=1}} i analizie sekwencji [[Kwas deoksyrybonukleinowy|DNA]]{{odn|Ghuman|Giaquinta|Tarhio|2014|s=1}}. Znalazły one również zastosowanie w generowaniu [[Cykl de Bruijna|ciągów de Bruijna]]{{odn|Radoszewski|2008|s=1}}.

== Zobacz też ==
* [[obrót bitowy]]
* [[transformata Burrowsa-Wheelera]]

== Uwagi ==
{{Uwagi
|potęga=Potęgowanie słów to ich wielokrotne złożenie, na przykład <math>(ma)^2 = mama</math><ref>{{Cytuj |autor=Jakub Radoszewski |tytuł=Kwadraty |czasopismo=Delta |data=marzec 2011 |url=http://www.deltami.edu.pl/temat/informatyka/algorytmy/2011/02/26/Kwadraty/ |data dostępu=2018-06-27}}</ref>.
|obrót cykliczny=Obrót cykliczny to słowo utworzone przez przeniesienie [[Podsłowo#Prefiks|prefiksu właściwego]] na koniec słowa{{odn|Grządko|2015|s=9}}.
}}

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{Cytuj |autor=Frédérique Bassino; Julien Clément; Cyril Nicaud |tytuł=The standard factorization of Lyndon words: an average point of view |czasopismo=Discrete Mathematics |wolumin=290 |numer=1 |data=28 stycznia 2005 |s=1–25 |doi=10.1016/j.disc.2004.11.002 |język=en |odn=tak}}
* {{Cytuj |autor=K. T. Chen; R. H. Fox; R. C. Lyndon |url=http://www.maths.ed.ac.uk/~v1ranick/papers/fox4.pdf |tytuł=Free differential calculus, IV. The quotient groups of the lower central series |czasopismo=Annals of Mathematics |wolumin=68 |numer=1 |data=lipiec 1958 |s=81–95 |doi=10.2307/1970044 |język=en |odn=tak}}
* {{Cytuj |autor=Jean-Pierre Duval |tytuł=Factorizing words over an ordered alphabet |czasopismo=Journal of Algorithms |wolumin=4 |numer=4 |data=grudzień 1983 |s=263–281 |doi=10.1016/0196-6774(83)90017-2 |język=en |odn=tak}}
* {{Cytuj |autor=Jean-Pierre Duval |tytuł=Génération d’une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée |czasopismo=Theoretical Computer Science |wolumin=60 |data=1988 |s=255–283 |doi=10.1016/0012-365X(78)90002-X |język=fr |odn=tak}}
* {{Cytuj |autor=Sukhpal Singh Ghuman; Emanuele Giaquinta; Jorma Tarhio |tytuł=Alternative Algorithms for Lyndon Factorization |czasopismo=arXiv.org |data=2014 |arxiv=1405.4892 |język=en |odn=tak}}
* {{Cytuj |autor=Łukasz Grządko |url=http://www.deltami.edu.pl/temat/informatyka/algorytmy/2014/12/28/O_rozkladzie_slow_na_slowa_Lyndo/ |tytuł=O rozkładzie słów na słowa Lyndona |czasopismo=Delta |data=styczeń 2015 |data dostępu=2018-06-27 |odn=tak}}
* {{Cytuj |autor=Jacek Jagodziński |tytuł=Metody planowania ruchu układów bezdryfowych bazujące na algorytmie Lafferriera-Sussmanna |miejsce=Wrocław |data=2011 |opis=Praca doktorska |archiwum=http://web.archive.org/web/20180130130934/http://www.dbc.wroc.pl/Content/12242/jagodzinski_metody_PhD.pdf |odn=tak}}
* {{Cytuj |autor=R. C. Lyndon |tytuł=On Burnside’s Problem |czasopismo=Transactions of the American Mathematical Society |wolumin=77 |numer=2 |data=wrzesień 1954 |s=202–215 |doi=10.2307/1990868 |język=en |odn=tak}}
* {{Cytuj |autor=Sabrina Mantaci; Antonio Restivol; Giovanna Rosone; Marinell Sciortino |url=https://arxiv.org/pdf/1306.1366.pdf |tytuł=Sorting suffixes of a text via its Lyndon Factorization |czasopismo=Proceedings of the Prague Stringology Conference |data=2013 |arxiv=1306.1366 |odn=tak}}
* {{Cytuj |autor=Jakub Radoszewski |url=https://www.mimuw.edu.pl/~rytter/TEACHING/TEKSTY/radoszewski_mgr.pdf |tytuł=Generowanie minimalnych leksykograficznie ciągów de Bruijna za pomocą słów Lyndona |data=wrzesień 2008 |opublikowany=Uniwersytet Warszawski |odn=tak}}
* {{Cytuj |autor=Jakub Radoszewski |url=http://www.deltami.edu.pl/temat/informatyka/algorytmy/2014/12/28/Slowa_pierwsze/ |tytuł=Słowa pierwsze |czasopismo=Delta |data=grudzień 2010 |s=3–4 |data dostępu=2018-06-27 |odn=tak}}
* {{Cytuj |autor=A.I. Shirshov |url=https://www.turgor.ru/lktg/2012/2/media/Shirshov_Umbruch.pdf#page=69 |tytuł=Subalgebras of Free Lie Algebras |inni=M.R. Bremner (tłum.); M.V. Kochetov (tłum.) |data=2009 |wydawca=Springer |język=en |odn=tak}}
* {{Cytuj |autor=Анатолий Илларионович Ширшов |url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=sm&paperid=5381&option_lang=rus |tytuł=Подалгебры свободных лиевых алгебр |czasopismo=Матем. сб. |wolumin=33 |numer=2 |data=1953 |s=441–452 |język=ru |odn=tak}}

== Linki zewnętrzne ==
* {{Cytuj |autor=Amy Glen |url=https://amyglen.files.wordpress.com/2012/03/melbourne_talk_feb2012.pdf |tytuł=Combinatorics of Lyndon words |data=16 lutego 2012 |wydawca=Murdoch University |język=en}}
* {{Cytuj |autor=Tomasz Kociumaka; Jakub Radoszewski; Wojciech Rytter |tytuł=Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence |czasopismo=Combinatorial Pattern Matching |data=czerwiec 2014 |s=202–211 |doi=10.1007/978-3-319-07566-2_21 |url=https://www.mimuw.edu.pl/~kociumaka/files/cpm2014c.pdf |język=en}}
* {{Cytuj |autor=Arturo Carpi, Gabriele Fici, Štěpán Holub, Jakub Opršal, Marinella Sciortino |tytuł=Universal Lyndon Words |czasopismo=Lecture Notes in Computer Science |numer=8634 |s=135–146 |data=2014 |arxiv=1406.5895 |doi=10.1007/978-3-662-44522-8_12 |język=en}}
* {{Cytuj |autor=Guy Melançon; Christophe Reutenauer |tytuł=Lyndon words, free algebras and shuffles |czasopismo=Can. J. Math. |wolumin=XLI |numer=4 |data=1989 |s=577–591 |doi=10.4153/CJM-1989-025-2 |język=en}}

[[Kategoria:Języki formalne|Lyndona słowo]]