The standard factorization of Lyndon words: an average point of view

DOI10.1016/j.disc.2004.11.002zbMath1101.68742OpenAlexW2076392597MaRDI QIDQ1764900

Julien Clément, Frédérique Bassino, Cyril Nicaud

Publication date: 22 February 2005

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://hal-upec-upem.archives-ouvertes.fr/hal-00619337/file/hal.pdf

zbMATH Keywords

Lyndon wordAverage-case analysisAnalytic combinatoricsStandard factorizationSuccess run

Mathematics Subject Classification ID

Combinatorics on words (68R15) Permutations, words, matrices (05A05) Formal languages and automata (68Q45)

Related Items

Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences ⋮ Asymptotic behavior of some factorizations of random words ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ On the size of the smallest alphabet for Lyndon trees ⋮ Almost linear time computation of maximal repetitions in run length encoded strings ⋮ Longest Lyndon Substring After Edit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Average cost of Duval's algorithm for generating Lyndon words
• Smallest components in decomposable structures: Exp-log class
• The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields
• The Cycle Construction
• Factorizing words over an ordered alphabet
• Limit Law of the Length of the Standard Right Factor of a Lyndon Word
• Generating Lyndon brackets.
• On Burnside's Problem
• Free differential calculus. IV: The quotient groups of the lower central series