Conference item
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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 563.7KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.MFCS.2018.72
Authors
- Publisher:
- Schloss Dagstuhl
- Host title:
- 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
- Journal:
- 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) More from this journal
- Publication date:
- 2018-08-20
- Acceptance date:
- 2018-06-13
- DOI:
- Keywords:
- Pubs id:
-
pubs:892038
- UUID:
-
uuid:8af29e8a-5542-405f-8bd0-beee16dc481e
- Local pid:
-
pubs:892038
- Source identifiers:
-
892038
- Deposit date:
-
2018-08-01
Terms of use
- Copyright holder:
- Murawski et al
- Copyright date:
- 2018
- Notes:
-
© Andrzej S. Murawski, Steven J. Ramsay, and Nikos Tzevelekos;
licensed under Creative Commons License CC-BY
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record