Orbits of Abelian Automaton Groups

Automaton groups are a class of self-similar groups generated by invertible finite-state transducers [11]. Extending the results of Nekrashevych and Sidki [12], we describe a useful embedding of abelian automaton groups into a corresponding algebraic number field, and give a polynomial time algorithm to compute this embedding. We apply this technique to study iteration of transductions in abelian automaton groups. Specifically, properties of this number field lead to a polynomial-time algorithm for deciding when the orbits of a transduction are a rational relation. These algorithms were implemented in the SageMath computer algebra system and are available online [2].