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

Fernau, Henning ; Wolf, Petra

Synchronization of Deterministic Visibly Push-Down Automata

pdf-format:
LIPIcs-FSTTCS-2020-45.pdf (0.6 MB)

Abstract

We generalize the concept of synchronizing words for finite automata, which map all states of the automata to the same state, to deterministic visibly push-down automata. Here, a synchronizing word w does not only map all states to the same state but also fulfills some conditions on the stack content of each run after reading w. We consider three types of these stack constraints: after reading w, the stack (1) is empty in each run, (2) contains the same sequence of stack symbols in each run, or (3) contains an arbitrary sequence which is independent of the other runs. We show that in contrast to general deterministic push-down automata, it is decidable for deterministic visibly push-down automata whether there exists a synchronizing word with each of these stack constraints, more precisely, the problems are in EXPTIME. Under the constraint (1), the problem is even in P. For the sub-classes of deterministic very visibly push-down automata, the problem is in P for all three types of constraints. We further study variants of the synchronization problem where the number of turns in the stack height behavior caused by a synchronizing word is restricted, as well as the problem of synchronizing a variant of a sequential transducer, which shows some visibly behavior, by a word that synchronizes the states and produces the same output on all runs.

BibTeX - Entry

@InProceedings{fernau_et_al:LIPIcs:2020:13286,
  author =	{Henning Fernau and Petra Wolf},
  title =	{{Synchronization of Deterministic Visibly Push-Down Automata}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Nitin Saxena and Sunil Simon},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13286},
  URN =		{urn:nbn:de:0030-drops-132861},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.45},
  annote =	{Keywords: Synchronizing word, Deterministic visibly push-down automata, Deterministc finite atuomata, Finite-turn push-down automata, Sequential transducer, Computational complexity}
}

Keywords: Synchronizing word, Deterministic visibly push-down automata, Deterministc finite atuomata, Finite-turn push-down automata, Sequential transducer, Computational complexity
Collection: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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