Skip to Main content Skip to Navigation
Conference papers

Classification of Markov Sources Through Joint String Complexity: Theory and Experiments

Philippe Jacquet 1, 2, 3 Dimitrios Milioris 1, 2, 3, 4 Wojciech Szpankowski 5 
2 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We propose a classification test to discriminate Markov sources based on the joint string complexity. String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we define the joint string complexity as the cardinality of the set of words which both strings have in common. In this paper we analyze the average joint complexity when both strings are generated by two Markov sources. We provide fast converging asymptotic expansions and present some experimental results showing usefulness of the joint complexity to text discrimination.
Document type :
Conference papers
Complete list of metadata
Contributor : Dimitrios Milioris Connect in order to contact the contributor
Submitted on : Wednesday, November 13, 2013 - 6:22:00 PM
Last modification on : Sunday, June 26, 2022 - 12:00:02 PM


  • HAL Id : hal-00904144, version 1


Philippe Jacquet, Dimitrios Milioris, Wojciech Szpankowski. Classification of Markov Sources Through Joint String Complexity: Theory and Experiments. IEEE International Symposium on Information Theory, Jul 2013, Istanbul, Turkey. ⟨hal-00904144⟩



Record views