Université Lille1 - Sciences et Technologies Automates finis et compositions de codes Finite automata and compositions of codes 511.3 Machines séquentielles, Théorie des Text Electronic Thesis or Dissertation fr Les automates finis sont un outil de base en informatique théorique ayant donne lieu à de nombreuses applications. De façon générique, un automate fini est une structure comportant un nombre fini d'états reliés par des transitions étiquetées par un élément. On parlera de transducteur si cet élément est un couple de mots et d'automate avec multiplicités si cet élément est un nombre. En interprétant un mot infini comme un nombre réel, on peut utiliser les automates avec multiplicités pour définir des fonctions réelles à variables réelles. Nous établissons certains résultats concernant la continuité ou la dérivabilité de telles fonctions. Certaines familles de transductions rationnelles ont été caractérisées en termes de compositions de morphismes et de morphismes inverses. Nous étudions les compositions de morphismes injectifs et de morphismes injectifs inverses, puis celles de morphismes préfixes et de morphismes préfixes inverses. La notion de morphisme injectif est fortement liée à celle de code. Après avoir étudié un algorithme permettant de décider si un code fini peut être ou non décomposé en codes préfixes et suffixes, nous réfutons la conjecture supposant que tout code de trois mots admet une telle décomposition. Enfin, nous étudions la maximalité de la base de l'intersection de deux monoïdes libres engendrés par des codes rationnels maximaux. Nous donnons des familles de contre-exemples à la conjecture supposant cette base toujours maximale. Réciproquement, nous montrons de façon constructive que tous les codes rationnels peuvent être obtenus comme une telle base. Finalement, nous donnons une condition nécessaire et suffisante de maximalité de cette base. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/LIBRE/Th_Num/1995/50376-1995-289.pdf Derencourt Denis 1900-01-01 120553511 1995LIL10145 1995-01-01 Informatique Université Lille1 - Sciences et Technologies 026404184 Doctorat non oui ddc:510 ASCII PDF 9999