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.2020.33
URN: urn:nbn:de:0030-drops-127008
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12700/
Go to the corresponding LIPIcs Volume Portal

Fernau, Henning ; Wolf, Petra ; Yamakami, Tomoyuki

Synchronizing Deterministic Push-Down Automata Can Be Really Hard

pdf-format:
LIPIcs-MFCS-2020-33.pdf (0.6 MB)

Abstract

The question if a deterministic finite automaton admits a software reset in the form of a so-called synchronizing word can be answered in polynomial time. In this paper, we extend this algorithmic question to deterministic automata beyond finite automata. We prove that the question of synchronizability becomes undecidable even when looking at deterministic one-counter automata. This is also true for another classical mild extension of regularity, namely that of deterministic one-turn push-down automata. However, when we combine both restrictions, we arrive at scenarios with a PSPACE-complete (and hence decidable) synchronizability problem. Likewise, we arrive at a decidable synchronizability problem for (partially) blind deterministic counter automata.
There are several interpretations of what synchronizability should mean for deterministic push-down automata. This is depending on the role of the stack: should it be empty on synchronization, should it be always the same or is it arbitrary? For the automata classes studied in this paper, the complexity or decidability status of the synchronizability problem is mostly independent of this technicality, but we also discuss one class of automata where this makes a difference.

BibTeX - Entry

@InProceedings{fernau_et_al:LIPIcs:2020:12700,
  author =	{Henning Fernau and Petra Wolf and Tomoyuki Yamakami},
  title =	{{Synchronizing Deterministic Push-Down Automata Can Be Really Hard}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ΔΎ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12700},
  URN =		{urn:nbn:de:0030-drops-127008},
  doi =		{10.4230/LIPIcs.MFCS.2020.33},
  annote =	{Keywords: Synchronizing automaton, Reset sequence, Real-time deterministic push-down automaton, Finite-turn push-down automaton, Computability, Computational complexity}
}

Keywords: Synchronizing automaton, Reset sequence, Real-time deterministic push-down automaton, Finite-turn push-down automaton, Computability, Computational complexity
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

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