On prefix normal words and prefix normal forms
From MaRDI portal
Publication:729994
DOI10.1016/j.tcs.2016.10.015zbMath1355.68212arXiv1611.09017OpenAlexW2552316968MaRDI QIDQ729994
Joe Sawada, Gabriele Fici, Frank Ruskey, Péter Burcsi, Zsuzsanna Lipták
Publication date: 23 December 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.09017
enumerationLyndon wordsbinary jumbled pattern matchingbinary languagespre-necklacesprefix normal formsprefix normal words
Related Items (8)
Weighted prefix normal words: mind the gap ⋮ Leaf realization problem, caterpillar graphs and prefix normal words ⋮ Enumerating words with forbidden factors ⋮ Abelian antipowers in infinite words ⋮ Generating a Gray code for prefix normal words in amortized polylogarithmic time per word ⋮ On infinite prefix normal words ⋮ The asymptotic number of prefix normal words ⋮ Bubble-flip -- a new generation algorithm for prefix normal words
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Indexing permutations for binary strings
- Sub-quadratic time and linear space data structures for permutation matching in binary strings
- On approximate jumbled pattern matching in strings
- Scaled and permuted string matching
- Algorithmic complexity of protein identification: Combinatorics of weighted strings
- New algorithms for binary jumbled pattern matching
- Binary jumbled string matching for highly run-length compressible texts
- Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
- Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet
- Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
- ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
- Clustered Integer 3SUM via Additive Combinatorics
- Compressed representations of sequences and full-text indexes
- Generating necklaces
- On Combinatorial Generation of Prefix Normal Words
- On Prefix Normal Words
- UNAVOIDABLE SETS OF CONSTANT LENGTH
This page was built for publication: On prefix normal words and prefix normal forms
