| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Joint String Complexity for Markov Sources
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.
Cited literature [10 references]
https://hal.inria.fr/hal-01197224
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, September 11, 2015 - 12:54:42 PM
Last modification on : Sunday, August 22, 2021 - 11:10:02 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:32:54 AM
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, September 11, 2015 - 12:54:42 PM
Last modification on : Sunday, August 22, 2021 - 11:10:02 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:32:54 AM
File
dmAQ0123.pdf
Publisher files allowed on an open archive