{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-8656"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-8656","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Groups Generated by Automata Arising from Transformations of the Boundaries of Rooted Trees","abstract":"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 ﬁrst 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 coeﬃcients of a permutational polynomial f(x) ∈ Z[x] that are necessary and suﬃcient 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 aﬃne transformations of (Z/2Z)[[t]]. To our best knowledge, this is the ﬁrst realization of the rank 2 lamplighter group by a bireversible automaton.","abstract_html":"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 ﬁrst 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 coeﬃcients of a permutational polynomial f(x) ∈ Z[x] that are necessary and suﬃcient 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 aﬃne transformations of (Z/2Z)[[t]]. To our best knowledge, this is the ﬁrst realization of the rank 2 lamplighter group by a bireversible automaton.","abstract_has_math":false,"creators":["Ahmed, Elsayed"],"institution":"University of South Florida","degree_name":"Doctor of Philosophy (Ph.D.)","degree_level":"Dissertation","degree_discipline":"Mathematics and Statistics","degree_department":null,"school":null,"contributors":["Dmytro Savchuk, Ph.D.","Paul Rosen, Ph.D.","Nataša Jonoska, Ph.D.","Jean-François Biasse, Ph.D.","Milé Krajčevski, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-10-18T07:00:00Z","date_published":"2018-10-18T07:00:00Z","updated_at":"2026-11-19T08:44:00Z","subjects":["Bireversible Automata","Ergodicity","Lamplighter Group","Mealy Automata","Permutational Polynomials","Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/7459","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/7459","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-8656","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Dmytro Savchuk, Ph.D.","Paul Rosen, Ph.D.","Nataša Jonoska, Ph.D.","Jean-François Biasse, Ph.D.","Milé Krajčevski, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Ahmed, Elsayed"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-10-18T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics and Statistics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation","Ph.D."]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (Ph.D.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Bireversible Automata","Ergodicity","Lamplighter Group","Mealy Automata","Permutational Polynomials","Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/7459"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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 ﬁrst 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 coeﬃcients of a permutational polynomial f(x) ∈ Z[x] that are necessary and suﬃcient 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 aﬃne transformations of (Z/2Z)[[t]]. To our best knowledge, this is the ﬁrst realization of the rank 2 lamplighter group by a bireversible automaton."]},{"key":"dc:title","label":"Title","values":["Groups Generated by Automata Arising from Transformations of the Boundaries of Rooted Trees"]}]}],"canonical_facts":{"dc:contributor":["Dmytro Savchuk, Ph.D.","Paul Rosen, Ph.D.","Nataša Jonoska, Ph.D.","Jean-François Biasse, Ph.D.","Milé Krajčevski, Ph.D."],"dc:creator":["Ahmed, Elsayed"],"dc:date":["2018-10-18T07:00:00Z"],"dc:description":["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 ﬁrst 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 coeﬃcients of a permutational polynomial f(x) ∈ Z[x] that are necessary and suﬃcient 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 aﬃne transformations of (Z/2Z)[[t]]. To our best knowledge, this is the ﬁrst realization of the rank 2 lamplighter group by a bireversible automaton."],"dc:identifier":["https://digitalcommons.usf.edu/etd/7459"],"dc:subject":["Bireversible Automata","Ergodicity","Lamplighter Group","Mealy Automata","Permutational Polynomials","Mathematics"],"dc:title":["Groups Generated by Automata Arising from Transformations of the Boundaries of Rooted Trees"],"thesis:degree_discipline":["Mathematics and Statistics"],"thesis:degree_level":["Dissertation","Ph.D."],"thesis:degree_name":["Doctor of Philosophy (Ph.D.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:44:00Z"}