New Results on Register Automata
summary
Shows concrete complexity and decidability boundaries for automata over infinite alphabets: emptiness reduces to a finite-alphabet reachability via an r+1 name restriction; nondeterministic inclusion and equivalence are undecidable but equivalence of deterministic register automata in P holds; bisimilarity for register automata is in NP (via symbolic partial-permutation generators); pushdown register automata have decidable reachability using a 3r bound for pushdown reduction and EXPTIME procedures, while bisimilarity becomes undecidable.
AI-written summary · about