On average sequence complexity

DOI10.1016/J.TCS.2004.06.023MaRDI QIDQ703547zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Svante Janson, Stefano Lonardi, Wojciech Szpankowski

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

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

Recommendations

• Combinatorial Pattern Matching
• Joint string complexity for Markov sources
• Joint string complexity for Markov sources: small data matters
• scientific article; zbMATH DE number 503334
• A linearly computable measure of string complexity

Cites work

• scientific article; zbMATH DE number 3913713 (Why is no real title available?)
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 1336330 (Why is no real title available?)
• scientific article; zbMATH DE number 1740058 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 2089987 (Why is no real title available?)
• A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
• A Space-Economical Suffix Tree Construction Algorithm
• On the combinatorics of finite words
• On the maximum number of distinct factors of a binary string
• On-line construction of suffix trees
• Proof of a conjecture on word complexity
• Self-alignments in words and their applications
• Special issue: Average-case analysis of algorithms
• Strings with maximally many distinct subsequences and substrings
• Sublinear approximate string matching and biological applications

Cited in

(5)

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

This page was built for publication: On average sequence complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703547)