Abstract FR:

Dans cette thèse, nous introduisons la théorie des graphes rationnels (qui sont reconnus par des transducteurs avec sorties étiquetées). Il s'agit de graphes étiquetés dont les sommets sont des mots dans un monoi͏̈de libre. Cette famille est une extension de nombreuses familles de graphes infinis connues à ce jour (les graphes context free de Muller et Schupp, les graphes équationnels de courcelle, les graphes préfixes-reconnaissables de Caucal ou encore les graphes automatiques de Sénizergues). Nous exhiberons certaines de leurs propriétés, telles que l'indécidabilité de nombreuses questions, ou bien des caractérisations interne et externe. Nous étudierons quelques unes de lerus sous-familles : les arbres rationnels, les graphes rationnels déterministes, ainsi que les graphes rationnels dont les sommets sont dans un monoi͏̈de commutatif. Enfin, nous nous intéresserons à leurs traces (à savoir l'ensemble des étiquettes des chemins partant d'un sommet pour arrivier à un sommet) et nous démontrerons que ces traces coi͏̈ncident avec les langages contextuels