Joint String Complexity for Markov Sources

Philippe Jacquet 1 Wojciech Szpankowski 2
1 Alcatel-Lucent Bell Labs France [Nozay]
2 Department of Computer Science [Purdue]
Abstract : 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.
Keywords : saddle point method. double depoissonization double Mellin transform semi-complexity String complexity
Type de document :
Communication dans un congrès
Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.303-322, 2012, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01197224
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 11 septembre 2015 - 12:54:42
Dernière modification le : mardi 7 mars 2017 - 15:19:11
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:32:54

Fichier

dmAQ0123.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01197224, version 1

Collections

INSMI | TDS-MACS

Citation

Philippe Jacquet, Wojciech Szpankowski. Joint String Complexity for Markov Sources. Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.303-322, 2012, DMTCS Proceedings. 〈hal-01197224〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

140

Contact


archive-ouverte@inria.fr