No.1649
理論計算機科学の深化と応用
Theoretical Computer Science and Its Applications
RIMS 研究集会報告集
 　
2009/02/02〜2009/02/04
岩間　一雄
Kazuo Iwama
　
目　次
　
1. An Algorithm Which Generates the Linear Extensions of a d-Complete Poset with Uniform Probability (Theoretical Computer Science and Its Applications)---1
　　　　京都大学数理解析研究所 / 大阪府立工業高等専門学校　　　仲田 研登 / 岡村 修志　(NAKADA,KENTO / OKAMURA,SHUJI)
　
2. 玉と壷のモデルにおける玉の衝突について (理論計算機科学の深化と応用)---------------------------------------------------------------9
　　　　福岡教育大学数学教育講座　　　中田 寿夫　(NAKATA,Toshio)
　
3. Enhancing Cooperative Behavior for P2P Reputation Systems by Group Selection (Theoretical Computer Science and Its Applications)---17
　　　　/ / / /九州大学システム情報科学研究院　　　/ / / / 櫻井 幸一　(Ren,Yizhi / Li,Mingchu / Cui,Yongrui / Guo,Cheng / Sakurai,Kouichi)
　
4. A note on characterizations of context-free languages using insertion and locality (Theoretical Computer Science and Its Applications)---23
　　　　東京電機大学理工学部サイエンス学系　　　小野寺 薫　(Onodera,Kaoru)
　
5. 拡張範疇文法の能力について (理論計算機科学の深化と応用)--------------------------------------------------------------------------31
　　　　電気通信大学電気通信学研究科情報工学専攻　　　松原 俊一　(Matsubara,Shunichi)
　
6. 確率時間ゲーム理論による組込みシステムのモデル化, 仕様記述及び検証 (理論計算機科学の深化と応用)----------------------------------39
　　　　金沢大学自然科学研究科電子情報工学専攻 / 金沢大学自然科学研究科電子情報工学専攻　　　林 将志 / 山根 智　(Hayashi,Masashi / Yamane,Satoshi)
　
7. 確率時間CEGAR (理論計算機科学の深化と応用)---------------------------------------------------------------------------------------47
　　　　金沢大学自然科学研究科 / 金沢大学自然科学研究科 / 金沢大学自然科学研究科　　　森下 篤 / 駒形 龍太 / 山根 智　(Morimoto,Atsushi / Komagata,Ryota / Yamane,Satoshi)
　
8. 逆探索によるp4タイリングの列挙 (理論計算機科学の深化と応用)----------------------------------------------------------------------55
　　　　埼玉大学理工学研究科 / 埼玉大学理工学研究科　　　堀山 貴史 / 鮫島 真人　(HORIYAMA,Takashi / SAMEJIMA,Masato)
　
9. 絵画的迷路の作り方 (理論計算機科学の深化と応用)----------------------------------------------------------------------------------58
　　　　東京工業大学情報理工学研究科 / 北陸先端科学技術大学情報科学研究科　　　岡本 吉央 / 上原 隆平　(Okamoto,Yoshio / Uehara,Ryuhei)
　
10. Complexity of pleat folding (Theoretical Computer Science and Its Applications)-------------------------------------------------66
　　　　/ 北陸先端科学技術大学院大学情報科学研究科 / 東京大学情報理工学系研究科 / 北陸先端科学技術大学院大学情報科学研究科　　　伊藤 剛志 / 清見 礼 / 今堀 慎治 / 上原 隆平　(Ito,Tsuyoshi / Kiyomi,Masashi / Imahori,Shinji / Uehara,Ryuhei)
　
11. 配属人数下限付き研修医配属問題 (理論計算機科学の深化と応用)---------------------------------------------------------------------73
　　　　京都大学情報学研究科 / 京都大学学術情報メディアセンター / 京都大学情報学研究科　　　濱田 浩気 / 宮崎 修一 / 岩間 一雄　(Hamada,Koki / Miyazaki,Shuichi / Iwama,Kazuo)
　
12. 連を多く含む文字列発見のための探索的手法 (理論計算機科学の深化と応用)-----------------------------------------------------------81
　　　　東北大学情報科学研究科 / 東北大学情報科学研究科 / 九州大学システム情報科学研究院 / グーグル株式会社 / 東北大学情報科学研究科　　　松原 渉 / 草野 一彦 / 坂内 英夫 / 石野 明 / 篠原 歩　(Matsubara,Wataru / Kusano,Kazuhiko / Bannai,Hideo / Ishino,Akira / Shinohara,Ayumi)
　
13. トランスポゾンから導かれる演算により定義される整合括弧列のDNAモデルとチューリング・マシンの構成 (理論計算機科学の深化と応用)----89
　　　　日本大学文理学部情報システム解析学科　　　鈴木 理　(Suzuki,Osamu)
　
14. 形式言語による結び目の実現問題に関する幾つかの予想 (理論計算機科学の深化と応用)-------------------------------------------------97
　　　　日本大学総合基礎科学研究科地球情報数理科学専攻 / 日本大学文理学部情報システム解析学科 / 日本大学文理学部情報システム解析学科 / 日本大学文理学部情報システム解析学科 / 日本大学文理学部情報システム解析学科　　　上谷 雄一 / 岡田 蓉子 / 堀口 俊 / 前川 達也 / 鈴木 理　(Uetani,Yuichi / Okada,Yoshiko / Horiguti,Syun / Maekawa,Tatuya / Suzuki,Osamu)
　
15. 形式言語における区別・説明の無限過程の定式化 (理論計算機科学の深化と応用)------------------------------------------------------105
　　　　真理大學資訊工程學系　　　植村 仁　(Uemura,Jin)
　
16. Chaitin's halting probability Ω and halting problems (Theoretical Computer Science and Its Applications)----------------------113
　　　　中央大学研究開発機構　　　只木 孝太郎　(Tadaki,Kohtaro)
　
17. A Note on Automorphisms of Cellular Automata (Theoretical Computer Science and Its Applications)-------------------------------121
　　　　京都大学理学研究科 (元) / カールスルーエ大学情報学部　　　西尾 英之助 / ヴォルシュ トーマス　(Nishio,Hidenosuke / Worsch,Thomas)
　
18. An Improvement of the Soundness of a 3-bit PCP (Theoretical Computer Science and Its Applications)-----------------------------129
　　　　京都大学情報学研究科 / 京都大学情報学研究科 / 京都大学情報学研究科　　　木下 直紀 / 玉置 卓 / 岩間 一雄　(Kinoshita,Naoki / Tamaki,Suguru / Iwama,Kazuo)
　
19. 最大エントロピー原理に基づくオンライン学習 (理論計算機科学の深化と応用)--------------------------------------------------------137
　　　　九州大学システム情報科学府情報理学専攻 / 九州大学システム情報科学研究院情報理学部門 / 九州大学システム情報科学研究院情報理学部門　　　大田 貴文 / 畑埜 晃平 / 竹田 正幸　(Ohta,Takafumi / Hatano,Kohei / Takeda,Masayuki)
　
20. 正則グラフのデカルト冪に対するカービング幅 (理論計算機科学の深化と応用)--------------------------------------------------------145
　　　　群馬大学工学研究科 / 群馬大学工学研究科 / 群馬大学工学研究科　　　小澤 恭平 / 大舘 陽太 / 山崎 浩一　(Kozawa,Kyohei / Otachi,Yota / Yamazaki,Koichi)
　
21. 層別グラフにおける有向木被覆問題の近似について (理論計算機科学の深化と応用)----------------------------------------------------153
　　　　豊橋技術科学大学工学研究科情報工学専攻 / 豊橋技術科学大学工学部情報工学系　　　多田 哲馬 / 藤戸 敏弘　(Tada,Tetsuma / Fujito,Toshihiro)
　
22. Metropolis Walkのcover timeにおけるタイトな上界 (理論計算機科学の深化と応用)---------------------------------------------------160
　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　野中 良哲 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Nonaka,Yoshiaki / Ono,Hirotaka / Sadakane,Kunihiko / Yamashita,Masafumi)
　
23. 例数制限付き教示の複雑さ (理論計算機科学の深化と応用)--------------------------------------------------------------------------165
　　　　東北大学情報科学研究科 / 東北大学情報科学研究科　　　小林 隼人 / 篠原 歩　(Kobayashi,Hayato / Shinohara,Ayumi)
　
24. 置換のランク付けに対する$O$($n$log log$n$)ビット領域の線形時間アルゴリズム (理論計算機科学の深化と応用)------------------------173
　　　　東北大学工学部電気情報・物理工学科 / 東北大学情報科学研究科　　　須藤 郁弥 / 篠原 歩　(Suto,Fumiya / Shinohara,Ayumi)
　
25. 文字列の繰り返し構造の平均解析 (理論計算機科学の深化と応用)--------------------------------------------------------------------181
　　　　東北大学情報科学研究科 / 東北大学情報科学研究科 / グーグル株式会社 / 東北大学情報科学研究科　　　草野 一彦 / 松原 渉 / 石野 明 / 篠原 歩　(Kusano,Kazuhiko / Matsubara,Wataru / Ishino,Akira / Shinohara,Ayumi)
　
26. グラフ同型問題から環同型問題への新たな帰着 (理論計算機科学の深化と応用)--------------------------------------------------------189
　　　　東京工業大学理学部情報科学科　　　早坂 智行　(Hayasaka,Tomiyuki)
　
27. Anti-Webによる$H$-彩色に関する新たな階層構造の導出 (理論計算機科学の深化と応用)------------------------------------------------195
　　　　大阪電気通信大学工学研究科 / エフ・エックス・プラットフォーム株式会社 / 大阪電気通信大学工学研究科　　　庄司 將一 / 小西 宏 / 上嶋 章宏　(Shoji,Masakazu / Konishi,Hiroshi / Uejima,Akihiro)
　
28. 2点連結な直並列グラフ上の高速なランダムウォーク (理論計算機科学の深化と応用)---------------------------------------------------203
　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　穂坂 祐輔 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Hosaka,Yusuke / Ono,Hirotaka / Sadakane,Kunihiko / Yamashita,Masafumi)
　
29. 最小マンハッタンネットワーク問題の近似について (理論計算機科学の深化と応用)----------------------------------------------------210
　　　　九州工業大学情報工学府 / 九州工業大学情報工学研究院　　　山崎 康行 / 宮野 英次　(Yamasaki,Yasuyuki / Miyano,Eiji)
　
30. NFALSE : 多項式環に基づくより高速な公開鍵暗号 (理論計算機科学の深化と応用)-----------------------------------------------------217
　　　　東京工業大学情報理工学研究科 / 東京工業大学情報理工学研究科　　　草川 恵太 / 田中 圭介　(Xagawa,Keita / Tanaka,Keisuke)
　
31. 暗号化関数とその性質について : RSA関数とPaillier関数 (理論計算機科学の深化と応用)----------------------------------------------222
　　　　東京工業大学情報理工学研究科 / 東京工業大学情報理工学研究科　　　平野 貴人 / 田中 圭介　(Hirano,Takato / Tanaka,Keisuke)
　
32. A Random Oracle Model with Setting and Watching Queries (Theoretical Computer Science and Its Applications)--------------------229
　　　　東京工業大学情報理工学研究科 / 東京工業大学情報理工学研究科 / 東京工業大学情報理工学研究科　　　/ 沼山 晃 / 田中 圭介　(Larangeira,Mario / Numayama,Akira / Tanaka,Keisuke)
　
33. 距離$k$分割線と一般図形のゾーン図の存在と一意性について (理論計算機科学の深化と応用)-------------------------------------------236
　　　　中央大学理工学部情報工学科 / トロント大学計算機科学科 / 中央大学理工学研究科 / 東北大学情報科学研究科　　　今井 桂子 / 河村 彰星 / 村松 悠 / 徳山 豪　(Imai,Keiko / Kawamura,Akitoshi / Muramatsu,Yu / Tokuyama,Takeshi)
　
34. Nearest Larger Neighbors問題に対する効率の良いアルゴリズム (理論計算機科学の深化と応用)----------------------------------------244
　　　　北陸先端科学技術大学院大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科　　　野木 慶太 / 浅野 哲夫 / 清見 礼　(Nogi,Keita / Asano,Tetsuo / Kiyomi,Masashi)
　
35. 連続確率分布枝重み付きDAGに対する最長路長さ分布の計算 (理論計算機科学の深化と応用)---------------------------------------------252
　　　　九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　安藤 映 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Ando,Ei / Ono,Hirotaka / Sadakane,Kunihiko / Yamashita,Masafumi)