Les sous-décalages sont des ensembles de coloriages d'un groupe définis en excluant certains motifs, et munis d'une action de décalage. Ces objets apparaissent naturellement comme discrétisations de systèmes dynamiques : à partir d'une partition de l'espace, on associe à chaque point de ce-dernier la suite des partitions visitées sous l'action du système.Plusieurs résultats récents ont mis en évidence la riche interaction entre la dynamique des sous-décalages et leur propriétés algorithmiques. Un exemple remarquable est la classification des entropies des sous-décalages multidimensionnels de type fini comme l'ensemble des nombres récursivement énumérables à droite. Cette thèse s'intéresse aux sous-décalages avec une approche double : d'un côté on s'intéresse à leurs propriétés dynamiques et de l'autre on les étudie comme des modèles de calcul.Cette thèse contient plusieurs résultats : une condition combinatoire suffisante prouvant qu'un sous-décalage dans un groupe dénombrable est non-vide, un théorème de simulation qui réalise une action effective d'un groupe de type fini comme un facteur d'une sous-action d'un sous-décalage de type fini, une caractérisation de l'effectivité à l'aide de machines de Turing généralisées et l'indécidabilité du problème de torsion pour deux groupes, qui sont invariants de systèmes dynamiques.Comme corollaires de nos résultats, nous obtenons d'abord une preuve courte de l'existence de sous-décalages fortement apériodiques sur tout groupe dénombrable. Puis, dans le cas d'un produit semi-direct de la grille bidimensionnelle avec un groupe de type fini avec problème du mot décidable, nous montrons que le sous-décalage obtenu est de type fini. / Shift spaces are sets of colorings of a group which avoid a set of forbidden patterns and are endowed with a shift action. These spaces appear naturally as discrete versions of dynamical systems: they are obtained by partitioning the phase space and mapping each element into the sequence of partitions visited by its orbit.Severa! breakthroughs in this domain have pointed out the intricate relationship between dynamics of shift spaces and their computability properties. One remarkable example is the classification of the entropies of multidimensional subshifts of finite type as the set of right recursively enumerable numbers. This work explores shift spaces with a dual approach: on the one hand we are interested in their dynamical properties and on the ether hand we studythese abjects as computational models.Four salient results have been obtained as a result of this approach: (1) a combinatorial condition ensuring non-emptiness of subshifts on arbitrary countable groups; (2) a simulation theorem which realizes effective actions of finitely generated groups as factors of a subaction of a subshift of finite type; (3) a characterization of effectiveness with oracles using generalized Turing machines and (4) the undecidability of the torsion problem for two group invariants of shift spaces.As byproducts of these results we obtain a simple proof of the existence of strongly aperiodic subshifts in countable groups. Furthermore, we realize them as subshifts of finite type in the case of a semidirect product of a d-dimensional integer lattice with a finitely generated group with decida ble word problem whenever d> 1.

Ce travail est consacré à l'étude de systèmes de Lyndon (pour la relation d'ordre alterné) et àla dynamique symbolique des développements des nombres en base négative. Pour un réel ß > 1fixé, nous construisons un code préfixe récurrent positif permettant non seulement de montrerl'intrinsèque ergodicité du —ß-shift mais aussi de déterminer la fonction zêta qui lui est associée.Nous étudions les conditions pour lesquelles le —ß-shift possède la spécification.En outre, lorsque ß est strictement plus petit que le nombre d'or, le langage du —ß-shift admet desmots intransitifs. Cet état de fait engendre dans le système dynamique des cylindres négligeablespar rapport à la mesure d'entropie maximale. Ces cylindres génèrent sur Iß=[—ß/(ß+1),1/(ß+1)[ depetits intervalles de mesure nulle (la mesure considérée étant l'unique mesure ergodique sur Iß).Nous en faisons une étude détaillée, en particulier nous déterminons ces intervalles "trous".Par ailleurs, nous étudions l'unicité des systèmes de numération des entiers relatifs en base négative et nous montrons qu'à chaque mot de Lyndon correspond un tel système. / This work deals with the study of the Lyndon systems (for alternate order) and the symbolicdynamics of the expansions of real numbers in negative base. For a given real ß > 1, we showthe intrinsic ergodicity of the —ß-shift using a positive recurring prefix code and we determine theassociated zeta function. We study the conditions for which the —ß-shift admits the specificationproperty.Moreover, when ß is less than golden ratio, the language of the —ß-shift contains intransitive words.These words lead to some cylinders negligible with respect to the measure with maximal entropy.In the interval Iß=[—ß/(ß+1),1/(ß+1)[, these cylinders correspond to some gaps: small interval withmeasure zero (with respect to the unique ergodic measure on Iß). We make a detailed study ofthese gaps.Otherwise, we study the uniqueness of the number systems of integers in negative base and weshow that to each Lyndon word corresponds to a such system.

Ce travail de thèse porte sur la dynamique du flot linéaire des surfaces de translation et de sa renormalisation par le flot de Teichmüller introduite par H. Masur et W. Veech en 1982. Une version combinatoire de cette renormalisation, l'induction de Rauzy sur les échanges d'intervalles, fût introduite auparavant par G. Rauzy en 1979. D'une part, nous faisons une étude combinatoire des classes de Rauzy qui forment une partition de l'ensemble des permutations irréductibles et interviennent dans l'algorithme d'induction de Rauzy. Nous donnons une formule pour la cardinalité de chaque classe. D'autre part, nous étudions un modèle de billard infini périodique dans le plan appelé le "vent dans les arbres" introduit dans une version stochastique par P. et T. Ehrenfest en 1912 et par J. Hardy et J. Weber en 1980 dans la version périodique. Nous construisons une famille de directions pour lesquelles le flot du billard est divergent donnant ainsi des exemples de Z^2-cocycles divergents au-dessus d'échanges d'intervalles. De plus, nous démontrons que le taux polynomial de diffusion générique est 2/3 autrement dit que la distance maximale atteinte par une particule au temps t est de l'ordre de t^2/3. / In this thesis, we study the dynamics of the linear flow of translation surfaces and its renormalization by the Teichmüller flow introduced by H. Masur and W. Veech in 1982. A combinatorial version of the renormalization, the Rauzy induction on interval exchange transformations, was introduced by G. Rauzy in 1979. First of all, we consider the combinatorics of Rauzy classes which form a partition of the set of irreducible permutations and are part of the Rauzy induction. In a second time, we consider an infinite Z^2-periodic billiard in the plane called the wind-tree model. It was introduced in a stochastic version by P. and T. Ehrenfest in 1912 and in the periodic version by J. Hardy and J. Weber in 1980. We construct a family of directions for which the flow of the billiard is divergent and hence give examples of divergent Z^2-cocycles over interval exchange transformations. Moreover, we prove that the polynomial rate of diffusion is generically 2/3. In other words, the maximal distance reached by a particule below time t has the order of t^2/3.

We study cellular automata as discrete dynamical systems and in particular investigate under which conditions two cellular automata are topologically conjugate. Based on work of McKinsey, Tarski, Pierce and Head we introduce derivative algebras to study the topological structure of sofic shifts in dimension one. This allows us to classify periodic cellular automata on sofic shifts up to topological conjugacy based on the structure of their periodic points. We also get new conjugacy invariants in the general case. Based on a construction by Hanf and Halmos, we construct a pair of non-homeomorphic subshifts whose disjoint sums with themselves are homeomorphic. From this we can construct two cellular automata on homeomorphic state spaces for which all points have minimal period two, which are, however, not topologically conjugate. We apply our methods to classify the 256 elementary cellular automata with radius one over the binary alphabet up to topological conjugacy. By means of linear algebra over the field with two elements and identities between Fibonacci-polynomials we show that every conjugacy between rule 90 and rule 150 cannot have only a finite number of local rules. Finally, we look at the sequences of finite dynamical systems obtained by restricting cellular automata to spatially periodic points. If these sequences are termwise conjugate, we call the cellular automata conjugate on all tori. We then study the invariants under this notion of isomorphism. By means of an appropriately defined entropy, we can show that surjectivity is such an invariant.

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 / 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

We study cellular automata as discrete dynamical systems and in particular investigate under which conditions two cellular automata are topologically conjugate. Based on work of McKinsey, Tarski, Pierce and Head we introduce derivative algebras to study the topological structure of sofic shifts in dimension one. This allows us to classify periodic cellular automata on sofic shifts up to topological conjugacy based on the structure of their periodic points. We also get new conjugacy invariants in the general case. Based on a construction by Hanf and Halmos, we construct a pair of non-homeomorphic subshifts whose disjoint sums with themselves are homeomorphic. From this we can construct two cellular automata on homeomorphic state spaces for which all points have minimal period two, which are, however, not topologically conjugate. We apply our methods to classify the 256 elementary cellular automata with radius one over the binary alphabet up to topological conjugacy. By means of linear algebra over the field with two elements and identities between Fibonacci-polynomials we show that every conjugacy between rule 90 and rule 150 cannot have only a finite number of local rules. Finally, we look at the sequences of finite dynamical systems obtained by restricting cellular automata to spatially periodic points. If these sequences are termwise conjugate, we call the cellular automata conjugate on all tori. We then study the invariants under this notion of isomorphism. By means of an appropriately defined entropy, we can show that surjectivity is such an invariant.

Indiana University-Purdue University Indianapolis (IUPUI) / This paper is a study of the dynamics of a new family of maps from the complex plane to itself, which we call twisted tent maps. A twisted tent map is a complex generalization of a real tent map. The action of this map can be visualized as the complex scaling of the plane followed by folding the plane once. Most of the time, scaling by a complex number will \twist" the plane, hence the name. The "folding" both breaks analyticity (and even smoothness) and leads to interesting dynamics ranging from easily understood and highly geometric behavior to chaotic behavior and fractals.

En esta Tesis se aborda la estimación óptima de señales caóticas generadas por mapas unidimensionales y contaminadas por ruido aditivo blanco Gaussiano, desde el punto de vista de los dos marcos de inferencia estadística más extendidos: máxima verosimilitud (ML) y Bayesiano. Debido al elevado coste computacional de estos estimadores, se proponen asimismo diversos estimadores subóptimos, aunque computacionalmente eficientes, con un rendimiento similar al de los óptimos. Adicionalmente se analiza el problema de la estimación de los parámetros de un mapa caótico explotando la relación conocida entre muestras consecutivas de la secuencia caótica. Por último, se considera la aplicación de los estimadores anteriores al diseño de receptores para dos esquemas de comunicaciones caóticas diferentes: conmutación caótica y codificación simbólica o caótica. / This Thesis studies the optimal estimation of chaoticsignals generated iterating unidimensional maps and contaminated by additive white Gaussian noise, from the point of view of the two most common frameworks in statistical inference: maximum likelihood (ML) and Bayesian. Due to the high computational cost of optimum estimators, several suboptimal but computationally efficient estimators are proposed, which attain a similar performance as the optimum ones. Additionally, the estimation of the parameters of a chaotic map is analyzed, exploiting the known relation between consecutive samples of the chaotic sequence. Finally, we consider the application of the estimators developed in the design of receivers for two different schemes of chaotic communications: chaotic switching and symbolic or chaotic coding.