Joint string complexity for Markov sources: small data matters

DOI10.1016/J.TCS.2020.08.002MaRDI QIDQ2205940zbMATH OpenOpenAlexFDO

Authors Philippe Jacquet, Dimitris Milioris, Wojciech Szpankowski

Publication date 21 October 2020

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

Full work available at URL https://arxiv.org/abs/1805.09025

zbMATH Keywords

analytic information theorygenerating functionsjoint string complexityMarkov sourcesMellin transformsaddle-point methodssource discriminationstring complexitysuffix trees

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorics on words (68R15)

Abstract: String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we introduce the joint string complexity as the cardinality of a set of words that are common to both strings. String complexity finds a number of applications from capturing the richness of a language to finding similarities between two genome sequences. In this paper we analyze the joint string complexity when both strings are generated by Markov sources. We prove that the joint string complexity grows linearly (in terms of the string lengths) when both sources are statistically indistinguishable and sublinearly when sources are statistically not the same. Precise analysis of the joint string complexity turns out to be quite challenging requiring subtle singularity analysis and saddle point method over infinity many saddle points leading to novel oscillatory phenomena with single and double periodicities. To overcome these challenges, we apply powerful analytic techniques such as multivariate generating functions, multivariate depoissonization and Mellin transform, spectral matrix analysis, and complex asymptotic methods.

Recommendations

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

Cites work

• A linearly computable measure of string complexity
• Analysis of the average depth in a suffix tree under a Markov model
• Analytical depoissonization and its applications
• Asymptotical growth of a class of random trees
• Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Average profile of the Lempel-Ziv parsing scheme for a Markovian source
• Average Redundancy of the Shannon Code for Markov Sources
• Average size of a suffix tree for Markov sources
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 1740058 (Why is no real title available?)
• scientific article; zbMATH DE number 2089987 (Why is no real title available?)
• Joint string complexity for Markov sources
• Matrix Analysis
• Mellin transforms and asymptotics: Harmonic sums
• On average sequence complexity
• On classification with empirically observed statistics and universal data compression
• On pattern frequency occurrences in a Markovian sequence
• Towards more realistic probabilistic models for data structures: the external path length in tries under the Markov model

Cited in

(3)

• Joint string complexity for Markov sources
• Combinatorial Pattern Matching
• On average sequence complexity

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

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