35 Pages
English

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

-

35 Pages
English

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

##### Formal language

Informations

Exrait

Counting occurrences for a ﬁnite 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 ( nr ) = [ z n ] x 1 x r F ( z x 1      x r ) x 1 =  = x r =1