On average sequence complexity

DOI10.1016/j.tcs.2004.06.023zbMath1091.68086OpenAlexW2091472121WikidataQ56768682 ScholiaQ56768682MaRDI QIDQ703547

Wojciech Szpankowski, Stefano Lonardi, Svante Janson

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.06.023

zbMATH Keywords

suffix treeaverage string complexity

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (3)

New second-preimage attacks on hash functions ⋮ Sublinear algorithms for approximating string compressibility ⋮ Joint string complexity for Markov sources: small data matters

Cites Work

• On the combinatorics of finite words
• Sublinear approximate string matching and biological applications
• Strings with maximally many distinct subsequences and substrings
• Special issue: Average-case analysis of algorithms
• On-line construction of suffix trees
• On the maximum number of distinct factors of a binary string
• Self-alignments in words and their applications
• A Space-Economical Suffix Tree Construction Algorithm
• A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
• Proof of a conjecture on word complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On average sequence complexity