TY - GEN
T1 - Polynomial-time equivalence testing for deterministic fresh-register automata
AU - Murawski, Andrzej S.
AU - Ramsay, Steven J.
AU - Tzevelekos, Nikos
PY - 2018/8/1
Y1 - 2018/8/1
N2 - 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.
AB - 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.
KW - Automata over infinite alphabets
KW - Bisimilarity
KW - Computational group theory
KW - Language equivalence
UR - http://www.scopus.com/inward/record.url?scp=85053183014&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2018.72
DO - 10.4230/LIPIcs.MFCS.2018.72
M3 - Conference Contribution (Conference Proceeding)
AN - SCOPUS:85053183014
SN - 9783959770866
VL - 117
T3 - Leibniz International Proceedings in Informatics (LIPIcs)
BT - 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
A2 - Potapov, Igor
A2 - Worrell, James
A2 - Spirakis, Paul
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
Y2 - 27 August 2018 through 31 August 2018
ER -
