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.2016.15
URN: urn:nbn:de:0030-drops-64996
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6499/
Go to the corresponding LIPIcs Volume Portal

Babari, Parvaneh ; Quaas, Karin ; Shirmohammadi, Mahsa

Synchronizing Data Words for Register Automata

pdf-format:
LIPIcs-MFCS-2016-15.pdf (0.6 MB)

Abstract

Register automata (RAs) are finite automata extended with a finite set of registers to store and compare data. We study the concept of synchronizing data words in RAs: Does there exist a data word that sends all states of the RA to a single state?

For deterministic RAs with k registers (k-DRAs), we prove that inputting data words with 2k+1 distinct data, from the infinite data domain, is sufficient to synchronize. We show that the synchronizing problem for DRAs is in general PSPACE-complete, and is NLOGSPACE-complete for 1-DRAs. For nondeterministic RAs (NRAs), we show that Ackermann(n) distinct data (where n is the size of RA) might be necessary to synchronize. The synchronizing problem for NRAs is in general undecidable, however, we establish Ackermann-completeness of the problem for 1-NRAs. Our most substantial achievement is proving NEXPTIME-completeness of the length-bounded synchronizing problem in NRAs (length encoded in binary). A variant of this last construction allows to prove that the bounded universality problem in NRAs is co-NEXPTIME-complete.

BibTeX - Entry

@InProceedings{babari_et_al:LIPIcs:2016:6499,
  author =	{Parvaneh Babari and Karin Quaas and Mahsa Shirmohammadi},
  title =	{{Synchronizing Data Words for Register Automata}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6499},
  URN =		{urn:nbn:de:0030-drops-64996},
  doi =		{10.4230/LIPIcs.MFCS.2016.15},
  annote =	{Keywords: data words, register automata, synchronizing problem, Ackermann-completeness, bounded universality, regular-like expressions with squaring}
}

Keywords: data words, register automata, synchronizing problem, Ackermann-completeness, bounded universality, regular-like expressions with squaring
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

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