35 Pages
English
Gain access to the library to view online
Learn more

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

-

Gain access to the library to view online
Learn more
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

Informations

Published by
Reads 21
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 ( nr ) = [ z n ] x 1 x r F ( z x 1      x r ) x 1 =  = x r =1