We study invertible Mealy automata acting on finite binary words, viewed as automorphisms of the rooted infinite binary tree. We give a detailed structural characterization of the automata whose associated automaton groups are free Abelian, and use Groebner bases to determine the linear “residuation matrix” that encodes the recursive action of these automorphisms on subtrees.
There are several natural decision problems associated with the orbits of the automorphisms defined by these automata, such as orbit membership and the computation of “time stamps” (the first time a configuration appears along an orbit). We present some partial results concerning the computational complexity of these problems. Finally, we explore connections with canonical normal forms in the associated numeration systems, in the spirit of Knuth’s work from the 1960s.
This is joint work with Tim Becker and Chris Grossack.