2026-07-23T16:36:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9654 2024-03-06T10:44:38Z ddc:004 open_access

Polynomial-Time Equivalence Testing for Deterministic Fresh-Register Automata Murawski, Andrzej S. Ramsay, Steven J. Tzevelekos, Nikos automata over infinite alphabets language equivalence bisimilarity computational group theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrzej S. Murawski and Steven J. Ramsay and Nikos Tzevelekos 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.72 urn:nbn:de:0030-drops-96544 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.72 eng https://creativecommons.org/licenses/by/3.0/legalcode