Clump Combinatorics, Automata, and Word Asymptotics
Résumé
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.
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.