P(l)aying for synchronization

Two topics will be presented: synchronization games and synchronization costs. In a synchronization game on a deterministic finite automaton, there are two players, Alice (Synchronizer) and Bob (Desynchronizer), whose moves alternate. Alice who pays first wants to synchronize the given automaton, while Bob aims to make her task as hard as possible. We answer a few natural questions related to such games. Speaking about synchronization costs, we consider deterministic weighted automata, that is, deterministic automata in which each transition has a certain price being a non-negative integer. The problem is whether or not we can synchronize a given automaton within a given budget. We determine the complexity of this problem.