Automata groups, and more generally automatic actions, form a fundamental class of groups, due to their striking properties (Burnside groups, groups of intermediate growth), their applicability (encoding of dynamical systems), and their accessibility to computation (their elements are described by finite state automata). This proposal will explore, both theoretically and practically, the decidability and complexity of these groups’ first order logic, with applications to the isomorphism problem for subshifts.
