Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://hdl.handle.net/10995/102493
Название: P(l)aying for synchronization
Авторы: Fominykh, F. M.
Martyugin, P. V.
Volkov, M. V.
Дата публикации: 2013
Библиографическое описание: 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.
Аннотация: 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.
Ключевые слова: COMPUTATIONAL COMPLEXITY
DETERMINISTIC FINITE AUTOMATON
DETERMINISTIC WEIGHTED AUTOMATON
SYNCHRONIZATION GAME
SYNCHRONIZING AUTOMATON
URI: http://hdl.handle.net/10995/102493
Условия доступа: info:eu-repo/semantics/openAccess
Идентификатор SCOPUS: 84891459955
Идентификатор PURE: 877874
c8d8a3f0-0110-4a55-8721-9aec5b0f9b95
ISSN: 1290541
DOI: 10.1142/S0129054113400170
Располагается в коллекциях:Научные публикации, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-84891459955.pdf192,45 kBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.