Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 19 février 2008 à en , Pierre Nicodème nous parlera de : Counting occurrence of words in random texts

Résumé : We consider random texts generated by a Bernoulli source. We want to count simultaneously the number of occurrences of words within a finite set of words in a random text of size n. The use of generating functions permits to construct a multivariate function counting the occurrences in texts of all size from 0 to infinity. From there several techniques give access to texts of size n. We compute the multivariate generating function

  1. by the very elegant analytic inclusion-exclusion method that resorts to combinatorics.
  2. by constructing the Aho-Corasick automaton recognizing the words, and translating later to generating functions. We compare the complexity of these two methods.
[Joint work with F. Bassino, J. Clément and J. Fayolle].
Dernière modification : vendredi 16 juin 2017 Valid HTML 4.01! Valid CSS! Organisateurs : Cyril.Banderier & Gerard.Duchamp at lipn.univ-paris13.fr