This is based partly on joint work with Philipp Hieronymi.

We study the theory of (N, +, S_k, S_l) where S_k and S_l are, respectively, k-automatic and l-automatic predicates (and not semilinear). We present a proof that this theory is never decidable and work towards a characterization of when it defines multiplication, with the ultimate goal of completely characterizing these structures with regard to interdefinability.