Document Open Access Logo

Some Variations on Lyndon Words (Invited Talk)

Authors Francesco Dolce, Antonio Restivo, Christophe Reutenauer

PDF
Thumbnail PDF

File

LIPIcs.CPM.2019.2.pdf
  • Filesize: 440 kB
  • 14 pages

Document Identifiers

Author Details

Francesco Dolce
  • IRIF, Université Paris Diderot, France
Antonio Restivo
  • Dipartimento di Matematica e Informatica, Università degli Studi di Palermo, Italy
Christophe Reutenauer
  • LaCIM, Université du Québec À Montréal, Canada

Cite As Get BibTex

Francesco Dolce, Antonio Restivo, and Christophe Reutenauer. Some Variations on Lyndon Words (Invited Talk). In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CPM.2019.2

Abstract

In this paper we compare two finite words u and v by the lexicographical order of the infinite words u^omega and v^omega. Informally, we say that we compare u and v by the infinite order. We show several properties of Lyndon words expressed using this infinite order. The innovative aspect of this approach is that it allows to take into account also non trivial conditions on the prefixes of a word, instead that only on the suffixes. In particular, we derive a result of Ufnarovskij [V. Ufnarovskij, Combinatorial and asymptotic methods in algebra, 1995] that characterizes a Lyndon word as a word which is greater, with respect to the infinite order, than all its prefixes. Motivated by this result, we introduce the prefix standard permutation of a Lyndon word and the corresponding (left) Cartesian tree. We prove that the left Cartesian tree is equal to the left Lyndon tree, defined by the left standard factorization of Viennot [G. Viennot, Algèbres de Lie libres et monoïdes libres, 1978]. This result is dual with respect to a theorem of Hohlweg and Reutenauer [C. Hohlweg and C. Reutenauer, Lyndon words, permutations and trees, 2003].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics on words
Keywords
  • Lyndon words
  • Infinite words
  • Left Lyndon trees
  • Left Cartesian trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alberto Apostolico and Maxime Crochemore. Fast parallel Lyndon factorization with applications. Math. Systems Theory, 28(2):89-108, 1995. Google Scholar
  2. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. A new characterization of maximal repetitions by Lyndon trees. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 562-571. SIAM, Philadelphia, PA, 2015. Google Scholar
  3. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "runs" theorem. SIAM J. Comput., 46(5):1501-1514, 2017. Google Scholar
  4. George M. Bergman. Centralizers in free associative algebras. Trans. Amer. Math. Soc., 137:327-344, 1969. Google Scholar
  5. Jean Berstel, Aaron Lauve, Christophe Reutenauer, and Franco V. Saliola. Combinatorics on words, volume 27 of CRM Monograph Series. American Mathematical Society, Providence, RI, 2009. Google Scholar
  6. Silvia Bonomo, Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino. Sorting conjugates and suffixes of words in a multiset. Internat. J. Found. Comput. Sci., 25(8):1161-1175, 2014. Google Scholar
  7. Christian Choffrut and Juhani Karhumäki. Combinatorics of words. In Handbook of formal languages, Vol. 1, pages 329-438. Springer, Berlin, 1997. Google Scholar
  8. Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. The maximal number of cubic runs in a word. J. Comput. System Sci., 78(6):1828-1836, 2012. Google Scholar
  9. Maxime Crochemore and Luís M.S. Russo. Cartesian and Lyndon trees. Theoretical Computer Science, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2018.08.011.
  10. Francesco Dolce, Antonio Restivo, and Christophe Reutenauer. On generalized Lyndon words. TCS, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2018.12.015.
  11. Jean-Pierre Duval. Factorizing words over an ordered alphabet. J. Algorithms, 4(4):363-381, 1983. Google Scholar
  12. Ira M. Gessel, Antonio Restivo, and Christophe Reutenauer. A bijection between words and multisets of necklaces. European J. Combin., 33(7):1537-1546, 2012. Google Scholar
  13. Ira M. Gessel and Christophe Reutenauer. Counting permutations with given cycle structure and descent set. J. Combin. Theory Ser. A, 64(2):189-215, 1993. Google Scholar
  14. Raffaele Giancarlo, Giovanni Manzini, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino. Block sorting-based transformations on words: beyond the magic BWT. In Developments in language theory, volume 11088 of Lecture Notes in Comput. Sci., pages 1-17. Springer, Cham, 2018. Google Scholar
  15. Christophe Hohlweg and Christophe Reutenauer. Lyndon words, permutations and trees. Theoret. Comput. Sci., 307(1):173-178, 2003. Google Scholar
  16. Manfred Kufleinter. On bijective variants of the Burrows-Wheeler transform. In Proceedings of the Prage Stringology Conference 2009, pages 65-79, 2009. Google Scholar
  17. M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. Google Scholar
  18. M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2002. Google Scholar
  19. Roger C. Lyndon. On Burnside’s problem. Trans. Amer. Math. Soc., 77:202-215, 1954. Google Scholar
  20. Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino. An extension of the Burrows-Wheeler transform. Theoret. Comput. Sci., 387(3):298-312, 2007. Google Scholar
  21. Dominique Perrin and Antonio Restivo. Words. In Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), pages 485-539. CRC Press, Boca Raton, FL, 2015. Google Scholar
  22. Christophe Reutenauer. Mots de Lyndon généralisés. Sém. Lothar. Combin., 54:Art. B54h, 16, 2005/07. Google Scholar
  23. Victor A. Ufnarovskij. Combinatorial and asymptotic methods in algebra. In Algebra, VI, volume 57 of Encyclopaedia Math. Sci., pages 1-196. Springer, Berlin, 1995. Google Scholar
  24. Gérard Viennot. Algèbres de Lie libres et monoïdes libres, volume 691 of Lecture Notes in Mathematics. Springer, Berlin, 1978. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact