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

Abstract : This thesis is devoted to the study of subshifts, or symbolic dynamical systems, defined on some finitely presented monoids like $Z^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
Document type :
Theses
Complete list of metadatas

Cited literature [45 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00664331
Contributor : Abes Star <>
Submitted on : Monday, January 30, 2012 - 1:10:37 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM
Long-term archiving on : Wednesday, December 14, 2016 - 2:29:17 AM

File

TH2011PEST1004_complete.pdf
Version validated by the jury (STAR)

Identifiers

  • 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⟩

Share

Metrics

Record views

701

Files downloads

238