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.
Type de document :
Communication dans un congrès
AofA 2014 - 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Jun 2014, Paris, France. 2014
Liste complète des métadonnées

https://hal-polytechnique.archives-ouvertes.fr/hal-01018460
Contributeur : Dimitrios Milioris <>
Soumis le : jeudi 16 mars 2017 - 11:59:39
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : samedi 17 juin 2017 - 13:30:17

Fichier

Jacquet_Milioris_AOFA_2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01018460, version 1

Collections

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. 2014. 〈hal-01018460〉

Partager

Métriques

Consultations de la notice

533

Téléchargements de fichiers

119