On average sequence complexity

DOI10.1016/J.TCS.2004.06.023zbMATH Open1091.68086DBLPjournals/tcs/JansonLS04OpenAlexW2091472121WikidataQ56768682 ScholiaQ56768682MaRDI QIDQ703547FDOQ703547

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

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

zbMATH Keywords

suffix treeaverage string complexity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

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

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)