Polynomial-time equivalence testing for deterministic fresh-register automata

ABSTRACT. Register automata are one of the most studied automata models over infinite alphabets. The complexity of language equivalence for register automata is quite subtle. In general, the problem is undecidable but, in the deterministic case, it is known to be decidable and in NP. Here we propose a polynomial-time algorithm building upon automata- and group-theoretic techniques. The algorithm is applicable to standard register automata with a fixed number of registers as well as their variants with a variable number of registers and ability to generate fresh data values (fresh-register automata). To complement our findings, we also investigate the associated inclusion problem and show that it is PSPACE-complete. This is joint work with Andrzej Murawski and Steven Ramsay.

Authors

• Nikos Tzevelekos

Keywords

No keywords are indexed for this paper.