Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102493
Title: P(l)aying for synchronization
Authors: Fominykh, F. M.
Martyugin, P. V.
Volkov, M. V.
Issue Date: 2013
Citation: Fominykh F. M. P(l)aying for synchronization / F. M. Fominykh, P. V. Martyugin, M. V. Volkov. — DOI 10.1142/S0129054113400170 // International Journal of Foundations of Computer Science. — 2013. — Vol. 24. — Iss. 6. — P. 765-780.
Abstract: 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. © 2013 World Scientific Publishing Company.
Keywords: COMPUTATIONAL COMPLEXITY
DETERMINISTIC FINITE AUTOMATON
DETERMINISTIC WEIGHTED AUTOMATON
SYNCHRONIZATION GAME
SYNCHRONIZING AUTOMATON
URI: http://hdl.handle.net/10995/102493
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84891459955
PURE ID: 877874
c8d8a3f0-0110-4a55-8721-9aec5b0f9b95
ISSN: 1290541
DOI: 10.1142/S0129054113400170
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84891459955.pdf192,45 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.