WORD COMPLEXITY AND REPETITIONS IN WORDS

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)

zbMATH Keywords

subword complexityde Bruijn wordsLempel-Ziv complexityiterated morphismsrepetitions in words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (3)

Prefix-suffix square reduction ⋮ Fast algorithms for finding a minimum repetition representation of strings and trees ⋮ On the distribution function of the complexity of finite sequences

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

This page was built for publication: WORD COMPLEXITY AND REPETITIONS IN WORDS