DocumentCode :
640294
Title :
Classification of Markov sources through joint string complexity: Theory and experiments
Author :
Jacquet, Philippe ; Milioris, Dimitris ; Szpankowski, Wojciech
Author_Institution :
Bell Labs., Alcatel-Lucent, Nozay, France
fYear :
2013
fDate :
7-12 July 2013
Firstpage :
2289
Lastpage :
293
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.
Keywords :
Markov processes; computational complexity; Markov sources classification; asymptotic expansion; average joint complexity; joint string complexity; Complexity theory; Computational modeling; Eigenvalues and eigenfunctions; Information theory; Joints; Markov processes; Transforms;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on
Conference_Location :
Istanbul
ISSN :
2157-8095
Type :
conf
DOI :
10.1109/ISIT.2013.6620634
Filename :
6620634
Link To Document :
بازگشت