License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.72
URN: urn:nbn:de:0030-drops-96544
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9654/
Go to the corresponding LIPIcs Volume Portal

Murawski, Andrzej S. ; Ramsay, Steven J. ; Tzevelekos, Nikos

Polynomial-Time Equivalence Testing for Deterministic Fresh-Register Automata

pdf-format:
LIPIcs-MFCS-2018-72.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{murawski_et_al:LIPIcs:2018:9654,
  author =	{Andrzej S. Murawski and Steven J. Ramsay and Nikos Tzevelekos},
  title =	{{Polynomial-Time Equivalence Testing for Deterministic Fresh-Register Automata}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{72:1--72:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9654},
  URN =		{urn:nbn:de:0030-drops-96544},
  doi =		{10.4230/LIPIcs.MFCS.2018.72},
  annote =	{Keywords: automata over infinite alphabets, language equivalence, bisimilarity, computational group theory}
}

Keywords: automata over infinite alphabets, language equivalence, bisimilarity, computational group theory
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI