Waiting time distributions for pattern occurrence in a constrained sequence

Abstract : A binary sequence of zeros and ones is called a (d; k)-sequence if it does not contain runs of zeros of length either lessthan d or greater than k, where d and k are arbitrary, but fixed, non-negative integers and d < k. Such sequences find requires that (d; k)-sequences do not contain a specific pattern w. Therefore, distribution results concerning pattern occurrence in (d; k)-sequences are of interest. In this paper we study the distribution of the waiting time until the r-th occurrence of a pattern w in a random (d; k)-sequence generated by a Markov source. Numerical examples are also provided.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.305--320
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00966498
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 16:59:11
Dernière modification le : mercredi 29 novembre 2017 - 10:26:16
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:50:25

Fichier

635-2651-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966498, version 1

Collections

Citation

Valeri T. Stefanov, Wojciech Szpankowski. Waiting time distributions for pattern occurrence in a constrained sequence. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.305--320. 〈hal-00966498〉

Partager

Métriques

Consultations de la notice

98

Téléchargements de fichiers

323