The Lempel–Ziv Complexity of Fixed Points of Morphisms

DOI10.1137/050646846zbMath1138.68046OpenAlexW2025348860MaRDI QIDQ3503229

Sorin Constantinescu, Lucian Ilie

Publication date: 22 May 2008

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050646846

zbMATH Keywords

fixed pointsmorphismsinfinite wordsfactorscombinatorics on wordsLempelZiv complexity

Mathematics Subject Classification ID

Combinatorics on words (68R15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

A separation between RLSLPs and LZ77 ⋮ Logarithmic equal-letter runs for BWT of purely morphic words ⋮ String attractors and infinite words ⋮ Palindromic Ziv-Lempel and Crochemore factorizations of \(m\)-bonacci infinite words ⋮ On the distribution function of the complexity of finite sequences ⋮ Repetitions in strings: algorithms and combinatorics

This page was built for publication: The Lempel–Ziv Complexity of Fixed Points of Morphisms