Average cost of Duval's algorithm for generating Lyndon words

DOI10.1016/0304-3975(94)00013-1zbMath0938.68766OpenAlexW1994182156WikidataQ56030650 ScholiaQ56030650MaRDI QIDQ1334678

Jean Berstel, Michel Pocchiola

Publication date: 25 September 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00013-1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Related Items (4)

Unnamed Item ⋮ Computation of Maximal Determinants of Binary Circulant Matrices ⋮ The standard factorization of Lyndon words: an average point of view ⋮ Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence

Uses Software

• Maple

Cites Work

• Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée. (Generation of a section of conjugation classes and trees of Lyndon words of bounded length)
• Lexicographically least circular substrings
• Factorizing words over an ordered alphabet
• Singularity Analysis of Generating Functions
• Amortized Computational Complexity
• Generating necklaces
• Generating Binary Trees Lexicographically
• Constant Time Generation of Free Trees
• On Burnside's Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Average cost of Duval's algorithm for generating Lyndon words