Symbolic dynamics on multidimensional systems and infinite trees - Archive ouverte HAL Access content directly
Theses Year : 2011

Symbolic dynamics on multidimensional systems and infinite trees

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

(1)
1

Abstract

This thesis is devoted to the study of subshifts, or symbolic dynamical systems, defined on some finitely presented monoids like ℤ^d or the infinite binary tree. The main result concerning multidimensional subshifts establishes that any effective subshift of dimension d can be obtained by factor map and projective subaction of a subshift of finite type of dimension d+1. This result has many applications, and in particular we prove that multidimensional effective S-adic subshifts are sofic. On tree-shifts we prove a decompositiontheorem, which implies that the conjugacy problem between two tree-shifts of finite type is decidable. We then investigate the class of sofic tree-shifts that are exactly those recocognized by tree automata. We prove that any sofic tree-shift has a unique deterministic, reduced, irreducible and synchronized tree automaton that recognized it. Finally we prove that it is decidable wether a sofic tree-shift belong to the sub-class of AFT tree-shifts
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, ℤ^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
Fichier principal
Vignette du fichier
TH2011PEST1004_complete.pdf (1.62 Mo) Télécharger le fichier
Origin : Version validated by the jury (STAR)
Loading...

Dates and versions

pastel-00664331 , version 1 (30-01-2012)

Identifiers

  • HAL Id : pastel-00664331 , version 1

Cite

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⟩
322 View
238 Download

Share

Gmail Facebook Twitter LinkedIn More