Une première partie de l'exposé sera consacrée aux automates max-plus et min-plus. Ces automates apparaissent naturellement dans des problèmes d'ordonnancement et dans certains problèmes de la théorie des langages comme la puissance finie ou la hauteur d'étoile. Je montrerai comment décider si un automate max-plus d'ambiguïté bornée réalise une série intrinsèquement non ambiguë, ce qui permet d'étendre la classe de famille dans laquelle la séquentialité des séries rationnelles max-plus est décidable. Par ailleurs, je présenterai le résultat selon lequel toute série qui est à la fois une série rationnelle max-plus et min-plus est en fait une série non ambiguë. La seconde partie de l'exposé portera sur la notion de conjugaison d'automates avec multiplicités, inspirée par la celle de conjugaison des systèmes dynamiques. Nous verrons dans quelle mesure des automates qui réalisent des séries identiques peuvent être reliés par une chaîne de conjugaison. D'autre part, nous donnerons une interprétation de cette définition matricielle en termes de revêtements d'automates. Nous verrons enfin les conséquences de la combinaison de ces deux approches.

Le problème de l'exploration de graphes trouve ses motivations en informatique fondamentale, notamment en logique et en théorie de la complexité. Il possède également de nombreuses applications en robotique. Quel que soit le cadre, la quantité de mémoire utilisée par l'entité mobile (robot, automate fini, etc.) effectuant l'exploration est un des paramètres importants à considérer. Dans cette thèse, nous étudions en détail la complexité en espace de l'exploration de graphes, à travers différents modèles. Nous distinguons principalement deux cadres d'études.<br /><br />Dans la première partie de la thèse, nous nous attachons à l'étude de l'exploration ``sans assistance'', c'est-à-dire lorsque l'entité mobile ne possède aucune information sur le graphe à explorer. Dans ce contexte, nous prouvons plusieurs bornes inférieures et supérieures sur la quantité de mémoire nécessaire et suffisante à l'entité pour explorer tous les graphes. En particulier, nous montrons que l'algorithme très simple de parcours en profondeur d'abord est optimal en mémoire lorsque la complexité est exprimée en fonction du degré et du diamètre.<br /><br />Dans la seconde partie de la thèse, nous nous attachons à l'étude de l'exploration ``avec assistance''. Nous considérons un modèle supposant l'existence d'un oracle ayant une connaissance exhaustive du graphe exploré, et capable d'aider l'entité mobile en lui fournissant de l'information. Nous nous intéressons ainsi à la quantité minimale d'information (mesurée en nombre de bits) que l'oracle doit fournir à l'entité pour permettre l'exploration. Cette information peut être soit donnée directement à l'entité, soit codée sur les sommets du graphes.

Les automates cellulaires fournissent un cadre agréable et uniforme pour aborder une des problématiques majeures de l'étude des «systèmes complexes» : comprendre comment et pourquoi des systèmes qui possèdent un comportement microscopique -- local -- facile à décrire peuvent avoir un comportement macroscopique -- global -- beaucoup plus compliqué. Depuis leur introduction dans les années 40, de nombreux travaux ont été entrepris afin de comprendre les liens existant entres les propriétés locales et globales des automates cellulaires.<br /><br />Ces vingt dernières années est apparue une nouvelle approche à travers la recherche de classifications pertinentes des automates cellulaires. Ainsi, de nombreuses classifications formelles ont été proposées pour mieux cerner les comportements de type «chaotique», principalement à l'aide d'outils de nature topologique. Cependant, une autre forme d'automates cellulaires complexes -- les automates cellulaires pour lesquels semblent émerger des structures locales, des particules, qui interagissent selon des schémas complexes -- reste peu étudiée. A notre connaissance, seuls les travaux d'I. Rapaport proposent une classification -- le groupage -- de nature algébrique, inspirée par cette forme de complexité. Nos travaux consistent en la généralisation de cette classification, afin d'une part de prendre en compte certaines notions intéressante comme l'universalité intrinsèque et d'autre part de renforcer la structure algébrique qui fait la force de cet outil -- tout en conservant sa nature géométrique.<br /><br />Dans une première partie, la structure interne des automates cellulaires est étudiée et une nouvelle caractérisation des automates cellulaires de dimension donnée est proposée, mettant en avant la notion de sous-automate. Dans une deuxième partie, les transformations «géométriques» des automates cellulaires sont caractérisées et un modèle de groupage abstrait est défini. Fort de ces deux outils et de la notion de sous-automate, une première extension du groupage est définie. La pertinence de cette classification est illustrée par l'étude de familles classiques d'automates cellulaires dans ce cadre. L'absence de structure de treillis en sus de la structure de pré-ordre amène l'introduction d'une nouvelle généralisation qui induit une structure de demi-treillis par l'opération de produit cartésien. Des liens entre les idéaux de cette structure et des problèmes de décision sont mis en avant. L'objet de la troisième partie est la notion d'automate cellulaire intrinsèquement universel, qui joue un rôle privilégié dans le cadre du groupage généralisé. L'indécidabilité de l'appartenance à cette famille d'automates cellulaires est établie et deux exemples de petits automates cellulaires de dimension 1 intrinsèquement universels sont construits, dont un automate cellulaire à 6 états et voisinage de von Neumann, le plus petit connu à ce jour.

Ce travail part de l'observation d'un résultat de P. Robba établi en 1982 dont l'énoncé est le suivant : si l est un entier p-adique, alors la série (1+T)l à coefficients dans l'anneau des entiers p-adiques, réduite modulo p, est algébrique sur le corps des fractions rationnelles à coefficients dans le corps fini à p éléments si et seulement si l est rationnel. En remarquant que cette série a une expression très proche de celle d'un endomorphisme du groupe multiplicatif sur l'anneau des entiers p-adiques, on généralise ce résultat à une classe de groupes formels de Lubin-Tate dont le logarithme vérifie une certaine condition d'algébricité. Nous interprétons ensuite ce résultat via le foncteur XK de Fontaine et Wintenberger et en tirons des conséquences sur l'indépendance algébrique des automorphismes de corps locaux. Dans la deuxième partie de ce travail, nous établissons l'analogue du théorème de P. Robba dans le cas des modules de Drinfeld de rang 1 définis sur le complété P-adique de l'anneau des polynômes à coefficients dans un corps fini où P est un polynôme irréductible, unitaire et à coefficients dans ce même corps fini.

Cette thèse traite des langages reconnaissables de mots indexés par des ordinaux. Plusieurs classes d'automates qui reconnaissent de tels mots ont été introduites par Büchi. Elles diffèrent par la longueur des mots reconnus par les automates. Nous en utilisons quatre: la classe pour les mots de longueur , celle pour les mots de longueur inférieure à , où n est un entier naturel, celle pour les mots de longueur dénombrable, et celle pour les mots de longueur quelconque. Nous y ajoutons la classe des automates de Kleene traditionnelle, sur les mots finis. Nous remontrons que ces différentes définitions d'automates sont équivalentes, c'est-à-dire que données deux de ces classes et un automate d'une des deux, la restriction du langage reconnu par l'automate aux mots du domaine le plus petit des deux classes est la restriction du langage reconnu par un automate de l'autre classe au même domaine. Nous donnons également une présentation unifiée de la déterminisation pour chacune des classes qui reconnaît au plus des mots de longueur dénombrable. Les semigroupes finis sont un formalisme équivalent aux automates pour définir des ensembles de mots finis. Perrin, Pin et Wilke ont introduits des structures algébriques adaptées à l'étude des langages de mots de longueur , qui, quand elles sont finies, sont équivalentes aux automates. Nous généralisons l'approche algébrique de la théorie des langages reconnaissables de mots de longueur aux mots de longueur inférieure à , puis aux mots de longueur dénombrable. Pour cela, nous définissons deux structures algébriques, les -semigroupes et les -semigroupes, qui, quand elles sont finies, sont équivalentes respectivement aux automates pour les mots de longueur inférieure à et aux automates pour les mots de longueur dénombrable. Comme pour le cas des mots de longueur , une algèbre syntaxique peut être canoniquement associée à chaque langage reconnaissable. Nous définissons le produit de Schützenberger et le produit en couronne sur les -semigroupes. Nous étendons également le théorème des variétés d'Eilenberg aux mots de longueur dénombrable. Finalement, nous remontrons l'équivalence entre langages reconnus par automates et langages définis par énoncés de logique monadique du second ordre quand on s'intéresse aux mots de longueur dénombrable. Le théorème d'équivalence de Schützenberger entre langages sans étoile et semigroupes finis apériodiques est étendu aux mots de longueur inférieure à , et le théorème d'équivalence entre langages sans étoile et langages définis par énoncés de logique du premier ordre de l'ordre linéaire de McNaughton et Papert est étendu aux mots de longueur quelconque.

Une brèche est un ensemble de blocs anguleux noyés dans un ciment de nature variable. Les brèches hydrothermales sont générées par un processus de fracturation, de dissolution des fragments, ainsi que des changements de composition causés par des eaux souterraines sous pression à haute température. La nature de la majorité des processus impliqués dans la formation des brèches hydrothermales est bien comprise d'un point de vue géochimique et plusieurs modèles basés sur cette perspective existent. Par contre, il n'existe pas de modèles approchant ces processus d'un point de vue géométrique. Dans ce mémoire, nous proposons un modèle basé sur les automates cellulaires, capable de simuler les principaux processus qui interviennent dans la formation des brèches. Un automate cellulaire est un modèle discret qui consiste en une grille de cellules pouvant chacune prendre à un instant donné un nombre fini d'états. Le temps est également discret et l'état d'une cellule au temps t est fonction de l'état au temps t -1 d'un nombre fini de cellules appelé son voisinage. À chaque nouvelle unité de temps, les mêmes règles sont appliquées pour toutes les cellules de la grille, produisant une nouvelle génération de cellules dépendant entièrement de la génération précédente. Cette approche est compatible avec l'aspect discret de la dissolution des minéraux et permet l'étude de l'évolution géométrique de fragments de roche virtuelle. Plus spécifiquement, on veut mesurer la complexité morphologique des fragments par leur dimension fractale de bordure, une méthode de mesure utilisée sur des échantillons réels et permettant de valider notre modèle avec des données analogiques. Un simulateur a été conçu pour mettre en oeuvre un tel modèle. Celui-ci est codé en Java et l'interface graphique est en HTML. Des expériences sur le simulateur ont mis en évidence deux régimes de dissolution: l'un limité par la diffusion (Diffusion Limited Regime -DLR), l'autre cinétique. Le premier régime dépend de la surface exposée et on y observe l'arrondissement et le lissage progressif des fragments. Le second régime est indépendant de la surface et on observe la formation de cavités dendritiques et une augmentation progressive de la complexité morphologique. D'un point de vue géochimique, le régime DLR est dit «contrôlé par la surface» alors que le régime cinétique est dit «contrôlé par le transport». Les extensions possibles au modèle sont variées et nombreuses. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Brèche hydrothermale, Automate cellulaire, Modélisation, Dissolution, Dimension fractale.

No description available.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les travaux développés dans cette thèse empruntent trois directions principales. D'une part, une étude attentive des propriétés de l'automate universel d'un langage rationnel a été menée. Cet automate fini (introduit sous une forme sensiblement différente par J.H. Conway) accepte le langage et a la particularité de contenir l'image par morphisme de n'importe quel automate équivalent. Nous donnons un algorithme pour le construire à partir de l'automate minimal. L'exploitation des propriétés de l'automate universel d'un langage réversible nous a permis de montrer qu'il existe un sous-automate quasi-réversible (à partir duquel on peut facilement construire un automate réversible) de l'automate universel équivalent. De plus, il existe un tel sous-automate sur lequel on peut calculer une expression rationnelle qui représente le langageavec une hauteur d'étoile minimale. D'autre part, nous donnons un algorithme pour décider la séquentialité d'une série (max,+) ou (min,+) réalisée par par un automate sur un alphabet à une lettre. La complexité de cet algorithme ne dépend que de la structure de l'automate et non des valeurs des coefficients. Nous présentons aussi un algorithme qui permet de procéder directement à la déterminisation d'un automate réalisant une série séquentielle et, si ce n'est pas le cas, à l'obtention d'un automate équivalent non ambigu. Ce dernier point rejoint le résultat de Stéphane Gaubert qui montre qu'on peut obtenir une expression (et donc un automate) non ambiguë pour n'importe quel série (max,+) rationnelle sur une lettre. Enfin, nous proposons un algorithme pour construire, à partir d'une expression rationnelle avec multiplicité, un automate qui représente la même série. Cet algorithme, qui est la généralisation des travaux d'Antimirov, permet d'obtenir explicitement un ensemble fini d'expressions qui représentent un ensemble générateur du semi-module auquel appartiennent les quotients de la série rationnelle.