  Register automata are a basic model of computation over infinite alphabets.
Fresh-register automata extend register automata with the capability to
generate fresh symbols in order to model computational scenarios involving name
creation. This paper investigates the complexity of the bisimilarity problem
for classes of register and fresh-register automata. We examine all main
disciplines that have appeared in the literature: general register assignments;
assignments where duplicate register values are disallowed; and assignments
without duplicates in which registers cannot be empty. In the general case, we
show that the problem is EXPTIME-complete.
  However, the absence of duplicate values in registers enables us to identify
inherent symmetries inside the associated bisimulation relations, which can be
used to establish a polynomial bound on the depth of Attacker-winning
strategies. Furthermore, they enable a highly succinct representation of the
corresponding bisimulations. By exploiting results from group theory and
computational group theory, we can then show solvability in PSPACE and NP
respectively for the latter two register disciplines. In each case, we find
that freshness does not affect the complexity class of the problem.
  The results allow us to close a complexity gap for language equivalence of
deterministic register automata. We show that deterministic language
inequivalence for the no-duplicates fragment is NP-complete, which disproves an
old conjecture of Sakamoto.
  Finally, we discover that, unlike in the finite-alphabet case, the addition
of pushdown store makes bisimilarity undecidable, even in the case of visibly
pushdown storage.
