Słowo Lyndona
Słowo Lyndona lub słowo pierwsze – niepuste słowo spełniające dwa warunki[1]:
- jest pierwotne, tzn. nie można go przedstawić w postaci potęgi dla [a],
- wśród swoich cyklicznych obrotów[b] jest najmniejsze względem porządku leksykograficznego
Przykładowo dla alfabetu można utworzyć 8 słów Lyndona nie dłuższych niż 4 litery ułożonych w porządku leksykograficznym:
- [2].
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[1].
- 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[1].
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 a rozkład ten jest jednoznaczny jeśli spełnia warunek monotoniczności [1][3][4]. W literaturze wynik takiego podziału jest nazywany rozkładem Lyndona (ang. Lyndon factorization)[5] lub rozkładem standardowym (ang. standard factorization)[6].
- Twierdzenie 4
- Rozkład Lyndona można wyznaczyć w czasie liniowym[7].
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[8][9]. Zostały one również zdefiniowane w 1953 przez rosyjskiego matematyka Anatolija Szyrszowa jako poprawne słowa (ros. правильные слова)[10][11].
Efektywny algorytm na dzielenie słów na słowa Lyndona opublikował Jean-Pierre Duval w 1983[4][7], który działał w liniowym czasie i przy stałym zapotrzebowaniu na pamięć[12]. 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[13].
Jean-Pierre Duval opublikował w 1988 również algorytm na generowanie słów Lyndona dla podanego alfabetu i rozmiaru słów[14].
Zastosowanie
Słowa Lyndona są wynikiem zdefiniowania elementów bazy w wolnej algebrze Liego[15].
W kolejnych latach znalazły zastosowanie w algorytmach tekstowych stosowanych w informatyce i bioinformatyce, a zwłaszcza w sortowaniu[16] i analizie sekwencji DNA[12]. Znalazły one również zastosowanie w generowaniu ciągów de Bruijna[17].
Zobacz też
Uwagi
- ↑ Potęgowanie słów to ich wielokrotne złożenie, na przykład [18].
- ↑ Obrót cykliczny to słowo utworzone przez przeniesienie prefiksu właściwego na koniec słowa[4].
Przypisy
- ↑ a b c d Radoszewski 2010 ↓, s. 4.
- ↑ Duval 1988 ↓, s. 271.
- ↑ Chen, Fox i Lyndon 1958 ↓.
- ↑ a b c Grządko 2015 ↓, s. 9.
- ↑ Mantaci i in. 2013 ↓, s. 2.
- ↑ Bassino, Clément i Nicaud 2005 ↓, s. 3.
- ↑ a b Duval 1983 ↓.
- ↑ Lyndon 1954 ↓, s. 203.
- ↑ Bassino, Clément i Nicaud 2005 ↓, s. 1.
- ↑ Ширшов 1953 ↓, s. 441–442.
- ↑ Shirshov 2009 ↓, s. 66.
- ↑ a b Ghuman, Giaquinta i Tarhio 2014 ↓, s. 1.
- ↑ Ghuman, Giaquinta i Tarhio 2014 ↓, s. 2.
- ↑ Duval 1988 ↓.
- ↑ Jagodziński 2011 ↓, s. 12.
- ↑ Mantaci i in. 2013 ↓, s. 1.
- ↑ Radoszewski 2008 ↓, s. 1.
- ↑ Jakub Radoszewski, Kwadraty, „Delta”, marzec 2011 [dostęp 2018-06-27].
Bibliografia
- Frédérique Bassino, Julien Clément, Cyril Nicaud, 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. Chen, R.H. Fox, R.C. Lyndon, 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-Pierre Duval, 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-Pierre Duval, 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 Singh Ghuman, Emanuele Giaquinta, Jorma Tarhio, Alternative Algorithms for Lyndon Factorization, „arXiv.org”, 2014, arXiv:1405.4892 (ang.).
- Łukasz Grządko, O rozkładzie słów na słowa Lyndona, „Delta”, styczeń 2015 [dostęp 2018-06-27].
- Jacek Jagodziński, Metody planowania ruchu układów bezdryfowych bazujące na algorytmie Lafferriera-Sussmanna, Praca doktorska, Wrocław 2011 [zarchiwizowane 2018-01-30].
- R.C. Lyndon, On Burnside’s Problem, „Transactions of the American Mathematical Society”, 77 (2), 1954, s. 202–215, DOI: 10.2307/1990868, JSTOR: 1990868 (ang.).
- Sabrina Mantaci i inni, Sorting suffixes of a text via its Lyndon Factorization, „Proceedings of the Prague Stringology Conference”, 2013, arXiv:1306.1366.
- Jakub Radoszewski, Generowanie minimalnych leksykograficznie ciągów de Bruijna za pomocą słów Lyndona, Uniwersytet Warszawski, wrzesień 2008.
- Jakub Radoszewski, Słowa pierwsze, „Delta”, grudzień 2010, s. 3–4 [dostęp 2018-06-27].
- A.I. Shirshov, Subalgebras of Free Lie Algebras, M.R. Bremner (tłum.), M.V. Kochetov (tłum.), Springer, 2009 (ang.).
- Анатолий Илларионович Ширшов, Подалгебры свободных лиевых алгебр, „Матем. сб.”, 33 (2), 1953, s. 441–452 (ros.).
Linki zewnętrzne
- Amy Glen, Combinatorics of Lyndon words, Murdoch University, 16 lutego 2012 (ang.).
- Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, 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.).
- Arturo Carpi 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.).
- Guy Melançon, Christophe Reutenauer, Lyndon words, free algebras and shuffles, „Can. J. Math.”, XLI (4), 1989, s. 577–591, DOI: 10.4153/CJM-1989-025-2 (ang.).
Media użyte na tej stronie
