RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
Video Library
Archive
Most viewed videos

Search
RSS
New in collection





You may need the following programs to see the files






International workshop "Logical Models of Reasoning and Computation"
February 2, 2012 17:30, Moscow, Steklov Mathematical Institute
 


P(l)aying for synchronization

Mikhail Volkov

Ural Federal University, Ekaterinburg
Video records:
Flash Video 1,725.1 Mb
Flash Video 283.7 Mb
MP4 283.7 Mb

Number of views:
This page:290
Video files:79

Mikhail Volkov
Photo Gallery


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

Abstract: 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.

Language: English

SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2017