Title: A Language Hierarchy and Kitchens-Type Theorem for Self-Similar Groups,
Abstract: We generalize the notion of self-similar groups of infinite tree
automorphisms to allow for groups which are defined on a tree but do not act
faithfully on it. The elements of such a group correspond to labeled trees
which may be recognized by a tree automaton (e.g. Rabin, Büchi, etc.), or
considered as elements of a tree shift (e.g. of finite type, sofic) as in
symbolic dynamics. We give examples to show that the various classes of
self-similar groups defined in this way do not coincide. As the main result,
extending the classical result of Kitchens on one-dimensional group shifts, we
provide a sufficient condition for a self-similar group whose elements form a
sofic tree shift to be a tree shift of finite type. As an application, we show
that the closure of certain self-similar groups of tree automorphisms are not
Rabin-recognizable. \end{abstract}