In this dissertation we study groups of automorphisms of rooted trees arising from the transformations of the boundaries of these trees. The boundary of every regular rooted tree can be endowed with various algebraic structures. The transformations of these algebraic structures under certain conditions induce endomorphisms or automorphisms of the tree itself that can be described using the language of Mealy automata. This connection can be used to study boundarytransformations using the propertiesof the induced endomorphisms, or vice versa. We concentrate on two ways to interpret the boundary of the rooted d-regular tree. In the first approach discussed in detail in Chapter 3 we treat it as the ring Zd of d-adic integers. This is achieved by naturally identifying the nth level of the rooted d-ary tree with the ring Z/(dnZ). Under this interpretation we study transformations of Zd induced by polynomials in Z[x]. We show that they always induce endomorphisms of the tree, completely describe these endomorphisms using the language of automata and show that all of their sections are again induced by polynomials in Z[x] of the same degree. In the case of permutational polynomials acting on Zd by bijections the induced endomorphisms are automorphisms of the tree. For d = 2 such polynomials were completely characterized by Rivest in [Riv01]. As our main application we utilize the result of Rivest to derive the conditions on the coefficients of a permutational polynomial f(x) ∈ Z[x] that are necessary and sufficient for f to induce a level transitive automorphism of the binary tree, which is equivalent to the ergodicity of the action of f(x) on Z2 with respect to the normalized Haar measure. Such polynomials have applications in cryptography and are used in certain generators of random numbers. In the second approach, to be discussed in Chapter 4, we treat the boundary of the rooted binary tree as the ring (Z/2Z)[[t]] of formal power series over Z/2Z. This view allowed us to completely describe the structure of a certain group generated by a 4-state 2-letter bireversible automaton. Namely, we show that it is isomorphic to the lamplighter group (Z/2Z)2 ≀ Z of rank two. We show that the action of the generators of this group on the boundary of the tree can be induced by affine transformations of (Z/2Z)[[t]]. To our best knowledge, this is the first realization of the rank 2 lamplighter group by a bireversible automaton.

Dans cette thèse, on se propose d'étudier les automates de Mealy, c'est-à-dire des transducteurs complets déterministes lettre à lettre ayant même alphabet d'entrée et de sortie. Ces automates sont utilisés depuis les années 60 pour engendrer des (semi-)groupes qui ont parfois des propriétés remarquables, permettant ainsi de résoudre plusieurs problèmes ouverts en théorie des (semi-)groupes. Dans ce travail, on s’intéresse plus particulièrement aux apports possibles de l'informatique théorique à l'étude de ces (semi-)groupes engendrés par automate. La thèse présentée s'articule autours de deux grands axes. Le premier, qui correspond aux chapitres II et III, traite des problèmes de décision et plus spécifiquement du problème de Burnside dans le chapitre II et des points singuliers dans le chapitre III. Dans ces deux chapitres on met en lien des propriétés structurelles de l'automate avec des propriétés du groupe engendré ou de son action. Le second axe, représenté par le chapitre IV, se rapporte à la génération aléatoire de groupes finis. On cherche, en tirant des automates de Mealy aléatoirement dans des classes spécifiques, à engendrer des groupes finis, et on aboutit à un résultat de convergence pour la distribution ainsi obtenue. Ce résultat fait écho au théorème de Dixon pour les groupes de permutations aléatoires / In this thesis, we study Mealy automata, i.e. complete, deterministic, letter-to-letter transducers which have same input and output alphabet. These automata have been used since the 60s to generate (semi)groups that sometimes have remarkable properties, that were used to solve several open problems in (semi)group theory. In this work, we focus more specifically on the possible contributions that theoretical computer science can bring to the study of these automaton (semi)groups.The thesis consists of two main axis. The first one, which corresponds to the Chapters II and III, deals with decision problems and more precisely with the Burnside problem in Chapter II and with singular points in Chapter III. In these two chapters, we link structural properties of the automaton with properties of the generated group or of its action. The second axis, which comprises the Chapter IV, is related with random generation of finite groups. We seek, by drawing random Mealy automata in specific classes, to generate finite groups, and obtain a convergence result for the obtained distribution. This result echoes Dixon's theorem on random permutation groups