these

´UNIVERSITE PARIS. DIDEROT (Paris 7)´ECOLE DOCTORALE : Sciences math´ematiques de Paris CentreDOCTORATInformatiqueˆBENOIT RAZETMACHINESD’EILENBERGEFFECTIVESTh`ese dirig´ee par G´erard HUETSoutenue le 26 novembre 2009JURYMM. Jean-Marc Champarnaud RapporteurJean-Christophe Filliˆatre RapporteurChristine Paulin-Mohring RappG´erard Berry ExaminateurRoberto Di Cosmo ExamiAarne Ranta ExaminateurG´erard Huet Directeur de th`eseTable des mati`eresIntroduction 7I Langages R´eguliers, Automates Finis et Axiomatisations 131 Th´eories des langages r´eguliers et des automates finis . . . . . . . . . . . . . . . . 131.1 Semigroupe, mono¨ıde libre, mot, langage. . . . . . . . . . . . . . . . . . . 131.2 Expressions r´eguli`eres et langages r´eguliers . . . . . . . . . . . . . . . . . 141.3 Automates finis et langages reconnaissables . . . . . . . . . . . . . . . . . 151.4 Th´eor`eme de Kleene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Quelques axiomatisations des alg`ebres de Kleene . . . . . . . . . . . . . . . . . . 172.1 Axiomatisation des alg`ebres de Kleene par Kozen . . . . . . . . . . . . . . 182.2 des alg`ebres d’actions de Pratt . . . . . . . . . . . . . . . 222.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.4 Compl´ements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30II ...