Browse/search for people

Publication - Dr Steven Ramsay

    Polynomial-time equivalence testing for deterministic fresh-register automata

    Citation

    Murawski, AS, Ramsay, SJ & Tzevelekos, N, 2018, ‘Polynomial-time equivalence testing for deterministic fresh-register automata’. in: Igor Potapov, James Worrell, Paul Spirakis (eds) 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

    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.

    Full details in the University publications repository