Joint string complexity for Markov sources

MaRDI QIDQ2920863zbMATH OpenFDO

Authors Wojciech Szpankowski, Philippe Jacquet

Publication date 29 September 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAQ0123/0.html

zbMATH Keywords

double Mellin transformsaddle point methodstring complexitydouble depoissonizationsemi-complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial probability (60C05) Asymptotic enumeration (05A16) Combinatorics on words (68R15)

Recommendations

• Joint string complexity for Markov sources: small data matters
• Complexity of strings in the class of Markov sources
• Combinatorial Pattern Matching
• On average sequence complexity
• A linearly computable measure of string complexity

Cited in

(5)

• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• On average sequence complexity
• Complexity of strings in the class of Markov sources
• Joint string complexity for Markov sources: small data matters
• Combinatorial Pattern Matching

This page was built for publication: Joint string complexity for Markov sources

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