Counting occurrences for a finite set of words: an inclusion exclusion approach

Description

Niveau: Supérieur
Counting occurrences for a finite set of words: an inclusion-exclusion approach Pierre Nicodeme CNRS - LIX, Ecole polytechnique joint work with Frederique Bassino, Julien Clement and Julien Fayolle

• no word


• noonan-zeilberger


• regnier-szpankowski


• a? fl


• counting occurrences


• generating function


• formal languages


• chomsky-schutzenberger


• ababa ababa

Subjects

• Documents
• Education
• University
• Clement
• École polytechnique
• Nicodème
• Fayolle
• Generating function
• Formal language

Informations

• Published by: zauj
• Reads: 31
• Language: English

Exrait

Counting occurrences for a finite set of words: an inclusion-exclusion approach

PierreNicode`me

´ CNRS - LIX, Ecole polytechnique

joint work with Fre´de´riqueBassino,JulienCl´ement and Julien Fayolle

Problem setting

Compute separately the number of occurrences of a non-reduced set of words U in a random text under Bernoulli (non-uniform) model

Reduced set: no word is factor of another word

Methods

Reduced Non-Reduced

U = { aab ba bb } U = { aa aab bbaabb }

– Formallanguagesmanipulations(Re´gnier-Szpankowski)( it fails in the non-reduced case )

– Aho-Corasick(automaton)+Chomsky-Schu¨tzenberger

– Inclusion-Exclusion (Goulden-Jackson, Noonan-Zeilberger)

Analytic Aim

U = { u 1     u r } non-reduced set of words O ( n r ) : random variable counting the number of occurrences of the word u r in a random text of size n (Bernoulli model)

We want to compute F ( z  x 1      x r ) = X Pr( O ( n 1) = k 1      O ( n r ) = k r ) x k 1 1    x k r z n r k 1 ≥ 0  k r ≥ 0  n ≥ 0

From there E  O ( n 1) ×    × O ( n r )  = [ z n ] ∂ ∂ x 1  ∂ ∂ x r F ( z x 1      x r )  x 1 =  = x r =1