WORD COMPLEXITY AND REPETITIONS IN WORDS
From MaRDI portal
Publication:5696964
DOI10.1142/S0129054104002297zbMath1104.68089MaRDI QIDQ5696964
Zhang, Kaizhong, Lucian Ilie, Sheng Yu
Publication date: 19 October 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
subword complexity; de Bruijn words; Lempel-Ziv complexity; iterated morphisms; repetitions in words
68R15: Combinatorics on words
Related Items
On the distribution function of the complexity of finite sequences, Fast algorithms for finding a minimum repetition representation of strings and trees
Cites Work
- Unnamed Item
- An optimal algorithm for computing the repetitions in a word
- Optimal off-line detection of repetitions in a string
- Detecting leftmost maximal periodicities
- Squares, cubes, and time-space efficient string searching
- Sur un théorème de Thue
- Unending chess, symbolic dynamics and a problem in semi-groups
- An O(n log n) algorithm for finding all repetitions in a string
- On the Complexity of Finite Sequences
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- Information-Theoretic Limitations of Formal Systems
- The definition of random sequences
- Sequences with minimal block growth