Clump Combinatorics, Automata, and Word Asymptotics

Mireille Regnier 1, 2 Billy Fang 3, 2 Daria Iakovishina 1, 2
1 AMIB - Algorithms and Models for Integrative Biology
CNRS - Centre National de la Recherche Scientifique : UMR8623, Polytechnique - X, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Résumé : Ce papier étudie les occurrences d'un ensemble de mots dans un texte aléatoire, un modèle de probabilité sur les textes aléatoires étant donné. Les occurrences chevauchantes ou "clumps" jouent un rôle central, Ils apparaissent dans le calcul de quantités importantes en comptage , comme la probabilité d'apparition dans un texte d'un nombre donné d'occurrences. Ce papier étudie les propriétés combinatoires des clumps et décrit deux automates de clumps qui permettent un calcul efficace des séries génératrices de comptage.
Type de document :
Communication dans un congrès
Michael Drmota; Mark Ward. ANALCO'14, Jan 2014, Portland, United States. SIAM, 2014, 〈10.1137/1.9781611973204.6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00864645
Contributeur : Mireille Regnier <>
Soumis le : lundi 23 septembre 2013 - 08:46:52
Dernière modification le : jeudi 11 janvier 2018 - 06:23:08

Identifiants

Citation

Mireille Regnier, Billy Fang, Daria Iakovishina. Clump Combinatorics, Automata, and Word Asymptotics. Michael Drmota; Mark Ward. ANALCO'14, Jan 2014, Portland, United States. SIAM, 2014, 〈10.1137/1.9781611973204.6〉. 〈hal-00864645〉

Partager

Métriques

Consultations de la notice

509