Synchronizing Words for Timed and Weighted Automata

Abstract. The problem of synchronizing automata is concerned with the existence of a word that sends all states of the automaton to one and the same state. This problem has classically been studied for de-terministic complete finite automata, with polynomial bounds on the length of the shortest synchronizing word and the existence problem being NLOGSPACE-complete. In this paper we consider synchronizing-word problems for timed and weighted automata. We consider the synchronization problem in several variants and combinations of these, including deterministic and non-deterministic timed and weighted automata, synchronization to unique location with possibly different clock valuation or accumulated weight, as well as synchronization with a safety condition forbidding the automaton to visit states outside a safety-set during synchronization (e.g. energy constraints). For timed automata the synchronization problems are shown to be PSPACE-complete in the deterministic case, and undecidable in the non-deterministic case. For deterministic weighted automata, the synchro-nization problem is proven PSPACE-complete under energy constraints, and in 3-EXPSPACE under general safety constraints.