SCS Undergraduate Thesis Topics
|Tsutomu Okano||Klaus Sutner||Invertible Binary Transducers and the Automorphisms of the Binary Tree|
An invertible binary transducer is a type of Mealy machine that encodes automorphisms of the infinite binary tree. The subgroup of Aut(2*) generated by these automorphisms is called a transduction group. Group theorists have become interested in transduction groups because they provide answers to classical questions such as Burnside's problem and constructing groups of intermediate growth. We focus on abelian transduction groups to answer fundamental decidability questions and prove structure theorems. We also explore automata theoretic questions regarding relations on 2* induced by elements of a transduction group and attempt to determine when they are regular.