Contribution à l'étude de la dynamique d'un automate à mémoire

Abstract

Dans cette thèse, nous étudions la dynamique d’un automate à mémoire dont la fonction de transition est une fonction à seuil. Au chapitre 1, on présente différentes propriétés qui permettent de reconnaître ou de réaliser une fonction à seuil donnée. Au chapitre 2, nous rappelons les résultats essentiels concernant la dynamique des automates à mémoire linéaires. Le chapitre 3, est consacré à l’étude de deux familles d’automates à mémoire : les automates à mémoire palindromiques puis les automates à mémoire réversibles. Aux chapitres 4 et 5, on s’intéresse à la dynamique de deux familles d’automates à mémoire géométrique. Au chapitre 6, on ramène l’étude de la dynamique d’un automate à mémoire à seuil à la résolution d’un programme linéaire. On présente un algorithme qui pour un couple (k,p) permet de construire, s’il en existe, un automate à mémoire à seul de taille de mémoire k admettant un cycle de longueur p. Cet algorithme nous a permis, pour la première fois, de construire des familles d’automates admettant des cycles de longueur supérieure au double de la mémoire.