Education Commons^™

Groups And Semigroups Generated By Automata, David Mccune

Department of Mathematics: Dissertations, Theses, and Student Research

In this dissertation we classify the metabelian groups arising from a restricted class of invertible synchronous automata over a binary alphabet. We give faithful, self-similar actions of Heisenberg groups and upper triangular matrix groups. We introduce a new class of semigroups given by a restricted class of asynchronous automata. We call these semigroups ``expanding automaton semigroups''. We show that this class strictly contains the class of automaton semigroups, and we show that the class of asynchronous automaton semigroups strictly contains the class of expanding automaton semigroups. We demonstrate that undecidability arises in the actions of expanding automaton semigroups and semigroups …