Graduation Year


Document Type




Degree Granting Department

Mathematics and Statistics

Major Professor

Dmytro Savchuk


Algebra, Algorithm, Automaton, Binary, Self-similar


The class of groups generated by automata have been a source of many counterexamples in group theory. At the same time it is connected to other branches of mathematics, such as analysis, holomorphic dynamics, combinatorics, etc. A question that naturally arises is finding the ways to classify these groups. The task of a complete classification and understanding at the moment seems to be too ambitious, but it is reasonable to concentrate on some smaller subclasses of this class. One approach is to consider groups generated by small automata: the automata with k states over d-letter alphabet (so called, (k,d)-automata) with small values of k and d. Certain steps in this directions have been made already: All groups generated by (2,2)-automata have been classified, and groups generated by (3,2)-automata were studied. In this work we study the class of groups generated by (4,2)-automata. More specifically, we partition all such automata into equivalence classes up to symmetry and minimal symmetry (symmetric and minimally symmetric automata naturally generate isomorphic groups) and classify completely all finite groups generated by automata in this class. We also list all classes generating abelian groups. Another important result of the project is developing a database of (4,2)-automata and computational routines that represent a new effective tool for the search for (4,2)-automata generating groups with specific properties, which hopefully will lead to finding counterexamples of certain conjectures.

Included in

Mathematics Commons