>>> Complexity Seminar（臨時）のお知らせ <<< 

北陸先端大の石原先生のところを訪問さている Khoussainov 先生
が，東京を訪問される機会に講演してもらうことになりました．
急で申し訳ありませんが，是非，ご参加下さい．

渡辺

題目：  Games, Update Networks and Their Complexity
発表者：Bakhadyr Khoussainov
日時：２００１年１２月６日（木）１１時〜
場所：東京工業大学 西８ (W) 号館（１０階）コラボレーションルーム W1008

概要：

In 1992, motivated by the work of Gurevich and Harrington, McNaughton 
introduced games played on finite graphs. In the mid of the 90s Nerode, 
Remmel and Yakhnis used and studied these games noticing that these 
games can be used  to model concurrent, reactive and real time systems. 
These games can also be used in foundations of software verification 
and specification. We continue the study of these games and give game-
theoretic models of networks.  In particular, we show that there is a 
polynomial time algorithm that, given a game, decides whether or not 
the game is a network. The work is joint with Michael Dinneen (Auckland) 
and Hans Bodlaender (Utrecht).

以上．