Skip to Main content Skip to Navigation

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 ℤ^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 :
Complete list of metadata

Cited literature [45 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Monday, January 30, 2012 - 1:10:37 PM
Last modification on : Saturday, January 15, 2022 - 3:56:51 AM
Long-term archiving on: : Wednesday, December 14, 2016 - 2:29:17 AM


Version validated by the jury (STAR)


  • HAL Id : pastel-00664331, version 1


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⟩



Record views


Files downloads