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 stateorder 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 PSPACEcomplete we also observe NPcomplete 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 alphabetsize. 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:158:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771740},
ISSN = {18688969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13299},
URN = {urn:nbn:de:0030drops132998},
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 