2012/05/31 by Födor Fominykh, Pavel Martyugin, Mikhail Volkov · 1 citation
Computer Science · #cs.FL #cs.CC #msc:68Q45 #msc:68Q25 #acm:68Q45 #acm:68Q25
paper · pdf · doi:10.1142/s0129054113400170
published as Int. J. Found. Comput. Sci. 24 (2013), 765-780 · Version 1 (by Födor Fominykh and Mikhail Volkov): 12 pages, 5 figures, close to the version published in the Proceedings of the 17th International Conference on Implementation and Application of Automata (LNCS 7381). Version 2: 19 pages, 7 figures, one of the problems left open in Version 1 solved, submitted
arxiv created 2012/12/05 · arxiv updated 2014/11/25
Two topics are presented: synchronization games and synchronization costs. In a synchronization game on a deterministic finite automaton, there are two players, Alice and Bob, whose moves alternate. Alice 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 automata in which each transition has a certain price. The problem is whether or not a given automaton can be synchronized within a given budget. We determine the complexity of this problem. We also formulate a few open questions.