  A finitary automaton group is a group generated by an invertible,
deterministic finite-state letter-to-letter transducer whose only cycles are
self-loops at an identity state. We show that, for this presentation of finite
groups, the uniform word problem is coNP-complete. Here, the input consists of
a finitary automaton together with a finite state sequence and the question is
whether the sequence acts trivially on all input words. Additionally, we also
show that the respective compressed word problem, where the state sequence is
given as a straight-line program, is PSpace-complete. In both cases, we give a
direct reduction from the satisfiability problem for (quantified) boolean
formulae and we further show that the problems remain complete for their
respective classes if we restrict the input alphabet of the automata to a
binary one.
