these

THÈSEprésentée à l’École Normale Supérieure de Cachanpour obtenir le grade deDocteur de l’École Normale Supérieure de Cachanpar : Kumar Neeraj VERMASpécialité : INFORMATIQUEAutomates d’arbres bidirectionnels modulothéories équationnellesSoutenue le 30 septembre 2003 devant un jury composé de :Rémi GILLERON examinateurJean GOUBAULT-LARRECQ directeur de thèseDenis LUGIEZ rapporteurDale MILLER président du juryMichaël RUSINOWITCH rapporteurHelmut SEIDL examinateur2RemerciementsFirst of all I am extremely grateful to Jean Goubault-Larrecq for having supervised my thesisand trained me as a researcher. With him I also had my introduction to research during internshipsat Dyade and INRIA. His interest in and knowledge of wide variety of subjects in computer scienceand mathematics has always surprised me and inspired me. Also his enthusiasm for speaking on thesesubjects, as well as various non-academic subjects have helped me learn a lot. I thank him for hispatience and availability to help me and to answer my questions.I thank Dale Miller for being president of my PhD jury. I thank Denis Lugiez for accepting toreferee this thesis, as well as for discussions and for giving me new ideas through his work. I thankMichäel Rusinowitch for accepting to referee this thesis. Also thanks to Rémi Gilleron and HelmutSeidl for accepting to take part in my PhD jury.Thanks to Hubert Comon for numerous discussions, ideas, and his enthusiasm for working onproblems. I ...