On infinite prefix normal words
From MaRDI portal
Publication:5919082
DOI10.1016/j.tcs.2021.01.015zbMath1487.68186OpenAlexW2901727845MaRDI QIDQ5919082
Zsuzsanna Lipták, Ferdinando Cicalese, Massimiliano Rossi
Publication date: 15 February 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.01.015
lexicographic orderSturmian wordcombinatorics on wordsThue-Morse wordabelian complexityprefix normal wordpaperfolding word
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sub-quadratic time and linear space data structures for permutation matching in binary strings
- Efficient oracles for generating binary bubble languages
- Binary bubble languages and cool-lex order
- On approximate jumbled pattern matching in strings
- On prefix normal words and prefix normal forms
- On collapsing prefix normal words
- Binary jumbled pattern matching on trees and tree-like structures
- Infinite Lyndon words
- Leaf realization problem, caterpillar graphs and prefix normal words
- Abelian complexity of Thue-Morse word over a ternary alphabet
- The abelian complexity of the paperfolding word
- Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
- The asymptotic number of prefix normal words
- On the asymptotic abelian complexity of morphic words
- New algorithms for binary jumbled pattern matching
- Inequalities characterizing standard Sturmian and episturmian words
- Computing abelian complexity of binary uniform morphic words
- Abelian Complexity and Frequencies of Letters in Infinite Words
- ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
- Clustered Integer 3SUM via Additive Combinatorics
- Abelian complexity of minimal subshifts
- Generating necklaces
- Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings
- A Lower Bound for Jumbled Indexing
- On Combinatorial Generation of Prefix Normal Words
- On Hardness of Jumbled Indexing
- On Prefix Normal Words
- Abelian complexity function of the Tribonacci word
- On infinite prefix normal words
- Bubble-flip -- a new generation algorithm for prefix normal words