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 ^{1}; Wojciech Szpankowski ^{2}
NULL##NULL
Philippe Jacquet;Wojciech Szpankowski
1 AlcatelLucent Bell Labs France [Nozay]
2 Department of Computer Science [Purdue]
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 semicomplexity}$ 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 semicomplexity 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)
Some Computable Complexity Measures for Binary Sequences
2 Documents citing this article
Source : OpenCitations
Milioris, Dimitrios, 2017, Joint Sequence Complexity: Introduction And Theory, Topic Detection And Classification In Social Networks, pp. 2156, 10.1007/9783319664149_3.
Milioris, Dimitrios; Jacquet, Philippe, 2014, Joint Sequence Complexity Analysis: Application To Social Networks Information Flow, Bell Labs Technical Journal, 18, 4, pp. 7588, 10.1002/bltj.21647.