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

Wolf, Petra

Synchronization Under Dynamic Constraints

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

Abstract

We introduce a new natural variant of the synchronization problem. Our aim is to model different constraints on the order in which a potential synchronizing word might traverse through the states. We discuss how a word can induce a state-order and examine the computational complexity of different variants of the problem whether an automaton can be synchronized with a word of which the induced order agrees with a given relation. While most of the problems are PSPACE-complete we also observe NP-complete variants and variants solvable in polynomial time. One of them is the careful synchronization problem for partial weakly acyclic automata (which are partial automata whose states can be ordered such that no transition leads to a smaller state), which is shown to be solvable in time ?(k² n²) where n is the size of the state set and k is the alphabet-size. The algorithm even computes a synchronizing word as a witness. This is quite surprising as the careful synchronization problem uses to be a hard problem for most classes of automata. We will also observe a drop in the complexity if we track the orders of states on several paths simultaneously instead of tracking the set of active states. Further, we give upper bounds on the length of a synchronizing word depending on the size of the input relation and show that (despite the partiality) the bound of the Černý conjecture also holds for partial weakly acyclic automata.

BibTeX - Entry

@InProceedings{wolf:LIPIcs:2020:13299,
  author =	{Petra Wolf},
  title =	{{Synchronization Under Dynamic Constraints}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{58:1--58:14},
  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/13299},
  URN =		{urn:nbn:de:0030-drops-132998},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.58},
  annote =	{Keywords: Synchronizing automaton, Čern{\'y} conjecture, Reset sequence, Dynamic constraints, Computational complexity}
}

Keywords: Synchronizing automaton, Černý conjecture, Reset sequence, Dynamic constraints, 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