Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence
From MaRDI portal
Publication:2830442
DOI10.1137/15M1043248zbMath1353.68226arXiv1510.02637MaRDI QIDQ2830442
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter
Publication date: 28 October 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1510.02637
Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Formal languages and automata (68Q45) Algorithms on strings (68W32)
Related Items (2)
Finding the largest fixed-density necklace and Lyndon word ⋮ Ranking and unranking fixed-density necklaces and Lyndon words
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extracting powers and periods in a word from its runs structure
- An algorithm for generating necklaces of beads in two colors
- 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)
- Universal cycles for combinatorial structures
- Necklaces of beads in k colors and k-ary de Bruijn sequences
- Average cost of Duval's algorithm for generating Lyndon words
- De Bruijn sequences with efficient decoding algorithms
- Generalized de Bruijn words for primitive words and powers
- Generation of the Ford sequence of length \(2^ n\), n large
- An algorithm for division of powerseries
- Factorizing words over an ordered alphabet
- A new memoryless algorithm for de Bruijn sequences
- Generating necklaces
- Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
- A method for constructing decodable de Bruijn sequences
- An Efficient Algorithm for Generating Necklaces with Fixed Density
- Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence
- Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
- Suffixes, Conjugates and Lyndon Words
- How Fast Can We Multiply Large Integers on an Actual Computer?
- Algorithms on Strings
- The lexicographically least de Bruijn cycle
- Lyndon Words and Short Superstrings
- On Burnside's Problem
- Free differential calculus. IV: The quotient groups of the lower central series
This page was built for publication: Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence
