Skip to Main content Skip to Navigation

Distribution de valuations sur les arbres.

Abstract : This thesis studies the limit distribution of parameters recursively defined on trees (rooted graphs). A first parameter which is studied is the result of arithmetical expressions drawn at random. An application is the heuristic improvement of an algorithm of research of RNA secondary structures. Another parameter I study is the size of logical or arithmetical expressions reduced according to idempotent, nilpotent or absorption laws. I study polynomial functionals of standard Brownian motion, of Brownian bridge, meander and excursion with the use of the method of moments which relies on generating functions and singularity analysis. I obtain the Gaussian limit of the joint law of the size and the internal path length of tries with Bernoulli source by using fixed point methods.
Document type :
Complete list of metadata
Contributor : Ecole Polytechnique Connect in order to contact the contributor
Submitted on : Wednesday, July 21, 2010 - 2:58:42 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on: : Friday, October 22, 2010 - 3:16:07 PM


  • HAL Id : pastel-00000839, version 1



Michel Nguyên-Thê. Distribution de valuations sur les arbres.. Informatique [cs]. Ecole Polytechnique X, 2004. Français. ⟨pastel-00000839⟩



Record views


Files downloads