Dynamique symbolique des systèmes 2D et des arbres infinis

Résumé : Cette thèse est consacrée à l'étude des décalages, ou encore systèmes dynamiques symboliques, définis sur certains monoïdes finiment présentés, $Z^d$ d'une part et les arbres d'autre part. Le principal résultat concernant les décalages multidimensionnels établit que tout décalage effectif de dimension d est obtenu par facteur et sous-action projective d'un décalage de type fini de dimension d+1. De ce résultat nous déduisons que les décalages S-adiques multidimensionnels donnés par une suite effective de substitutions sont sofiques. Sur les décalages d'arbres nous montrons un théorème de décomposition, qui permet d'écrire une conjugaison entre deux décalages d'arbres quelconques comme une suite finie d'opérations élémentaires, les fusions entrantes et les éclatements entrants. De ce théorème, associé à la commutation des fusions entrantes, nous déduisons la décidabilité du problème de conjugaison entre deux décalages d'arbres de type fini. Nous nous intéressons ensuite à la classe des décalages d'arbres sofiques, qui sont exactement ceux reconnus par des automates d'arbres montants dans lesquels tous les états sont à la fois initiaux et finaux. Nous montrons l'existence d'un unique automate d'arbres déterministe, réduit, irréductible et synchronisé qui reconnaît un décalage d'arbres sofique. Enfin nous montrons que l'appartenance à la sous-classe des décalages d'arbres AFT est décidable
Type de document :
Thèse
Autre [cs.OH]. Université Paris-Est, 2011. Français. <NNT : 2011PEST1004>
Liste complète des métadonnées


https://pastel.archives-ouvertes.fr/pastel-00664331
Contributeur : Abes Star <>
Soumis le : lundi 30 janvier 2012 - 13:10:37
Dernière modification le : jeudi 22 juin 2017 - 14:10:22
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 02:29:17

Fichier

TH2011PEST1004_complete.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : pastel-00664331, version 1

Citation

Nathalie Aubrun. Dynamique symbolique des systèmes 2D et des arbres infinis. Autre [cs.OH]. Université Paris-Est, 2011. Français. <NNT : 2011PEST1004>. <pastel-00664331>

Partager

Métriques

Consultations de
la notice

509

Téléchargements du document

173