Information in Strings: Enumeration of Eulerian Paths and Eulerian Components in Markov Sequences

Abstract : In this paper, we evaluate the number of Eulerian circuits that can be obtained by an arbitrary rotation in a Markovian string, i.e., corresponding to a given Markovian type. Since all rotations do not result in an Eulerian circuit, but several of them, called Eulerian components; we also investigate the number of Eulerian components that result from a random rotation in a Markovian string. We consider the asymptotic behaviour of those quantities when the size of the string n tends to infinity. In particular we show that the average number of components tends to be in log V , where V is the size of a large alphabet, in the uniform case.
Complete list of metadatas

https://hal-polytechnique.archives-ouvertes.fr/hal-01018460
Contributor : Dimitrios Milioris <>
Submitted on : Thursday, March 16, 2017 - 11:59:39 AM
Last modification on : Tuesday, May 14, 2019 - 10:13:46 AM
Long-term archiving on : Saturday, June 17, 2017 - 1:30:17 PM

File

Jacquet_Milioris_AOFA_2014.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01018460, version 1

Citation

Philippe Jacquet, Dimitrios Milioris. Information in Strings: Enumeration of Eulerian Paths and Eulerian Components in Markov Sequences. AofA 2014 - 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Jun 2014, Paris, France. ⟨hal-01018460⟩

Share

Metrics

Record views

763

Files downloads

304