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
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : Given a set of words and a probability model for random texts, we are interested in the behavior of occurrences of the words in a random text. Clumps are shown here to play a central role in these problems. They can be used to calculate relevant quantities, such as the probability that a random text contains a given number of pattern word occurrences. We provide combinatorial properties and describe two clump automata that can be used to e fficiently calculate generating functions.
Complete list of metadatas

https://hal.inria.fr/hal-00864645
Contributor : Mireille Regnier <>
Submitted on : Monday, September 23, 2013 - 8:46:52 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM

Identifiers

Collections

Citation

Mireille Regnier, Billy Fang, Daria Iakovishina. Clump Combinatorics, Automata, and Word Asymptotics. ANALCO'14, Jan 2014, Portland, United States. ⟨10.1137/1.9781611973204.6⟩. ⟨hal-00864645⟩

Share

Metrics

Record views

609