Journée-séminaire de combinatoire

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

Le 19 février 2008 à 14h en B107, 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].

 [Slides.pdf]

Dernière modification : Thursday 21 November 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr