Philippe Jacquet ; Wojciech Szpankowski - Joint String Complexity for Markov Sources

dmtcs:3001 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.3001
Joint String Complexity for Markov Sources

Authors: Philippe Jacquet ; Wojciech Szpankowski

    String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we define $\textit{joint string complexity}$ as the set of words that are common to both strings. We also relax this definition and introduce $\textit{joint semi-complexity}$ restricted to the common words appearing at least twice in 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 joint complexity and joint semi-complexity when both strings are generated by a Markov source. The problem 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.


    Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
    Section: Proceedings
    Published on: January 1, 2012
    Imported on: January 31, 2017
    Keywords: saddle point method.,double depoissonization,double Mellin transform,semi-complexity,String complexity,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
    Fundings :
      Source : OpenAIRE Research Graph
    • Emerging Frontiers of Science of Information; Funder: National Science Foundation; Code: 0939370
    • Collaborative Research: Information Theory of Data Structures; Funder: National Science Foundation; Code: 0830140
    • Information Transfer in Biological Systems; Funder: National Science Foundation; Code: 0800568

    1 Document citing this article

    Share

    Consultation statistics

    This page has been seen 133 times.
    This article's PDF has been downloaded 126 times.