Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata
Contributor : Mireille Regnier Connect in order to contact the contributor
Submitted on : Monday, September 23, 2013 - 8:46:52 AM
Last modification on : Sunday, November 20, 2022 - 3:26:49 AM

Links full text




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⟩



Record views