No.1744
計算機科学とアルゴリズムの数理的基礎とその応用
Mathematical Foundations and Applications of Computer Science and Algorithms
RIMS 研究集会報告集
 　
2011/02/01〜2011/02/03
西野　哲朗
Tetsuro Nishino
　
目　次
　
1. 実時間最終状態受理式決定性限定1カウンタ変換器の多項式時間等価性判定アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)---1
　　　　電気通信大学大学院情報理工学研究科 / 東芝ソリューション株式会社 / 電気通信大学・中央大学研究開発機構 / 電気通信大学大学院情報理工学研究科　　　若月 光夫 / 清野 和司 / 富田 悦次 / 西野 哲朗　(Wakatsuki,Mitsuo / Seino,Kazushi / Tomita,Etsuji / Nishino,Tetsuro)
　
2. UML パッケージ図に対するグラフ文法(計算機科学とアルゴリズムの数理的基礎とその応用)-----------------------------------------------11
　　　　電気通信大学産学官連携センター / 電気通信大学情報理工学研究科 / 東洋大学工学部　　　後藤 隆彰 / 西野 哲朗 /土田 賢省　(Goto,Takaaki / Nishino,Tetsuro / Tsuchida,Kensei)
　
3. 動的リアルタイムハイブリッド CEGAR による動的再構成可能組込みシステムの設計検証 (計算機科学とアルゴリズムの数理的基礎とその応用)---15
　　　　金沢大学大学院自然科学研究科 / 金沢大学理工研究域　　　酒井 誠 / 山根 智　(Sakai,Makoto / Yamane,Satoshi)
　
4. 確率時間 WiGAR による PTCTL サブクラスのモデル検査 (計算機科学とアルゴリズムの数理的基礎とその応用)------------------------------25
　　　　金沢大学大学院自然科学研究科 / 金沢大学大学院自然科学研究科 / 金沢大学理工研究域　　　高橋 正樹 / 清水 隆也 / 山根 智　(Takahashi,Masaki / Shimizu,Takaya / Yamane,Satoshi)
　
5. ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)------------------------------------------------------------35
　　　　科学技術振興機構ERATO湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科 / 科学技術振興機構ERATO湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科 / 北海道大学大学院情報科学研究科 / 北海道大学大学院情報科学研究科・科学技術振興機構ERATO湊離散構造処理系プロジェクト・ /科学技術振興機構ERATO湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科　　　川原 純 / 斎藤 寿樹 / 鈴木 拡 / 湊 真一 / 吉仲 亮　(Kawahara,Jun / Saitoh,Toshiki / Suzuki,Hiromu / Minato,Shin-ichi / Yoshinaka,Ryo)
　
6. Trevisan's extractor in the presence of quantum side information (Mathematical Foundations and Applications of Computer Science and Algorithms)---42
　　　　/ 東京工業大学情報理工学研究科 / /　　　De,Anindya / Portmann,Christopher / Vidick,Thomas / Renner,Renato
　
7. UNO は一人でも難しい (計算機科学とアルゴリズムの数理的基礎とその応用)------------------------------------------------------------48
　　　　マサチューセッツ工科大学 / マサチューセッツ工科大学 / 北陸先端科学技術大学院大学情報科学 / 国立情報学研究所 / 大阪府大学理学系　　　Demaine Erik D. / Demaine Martin L. / 上原 隆平 / 宇野 毅明 / 宇野 裕之　(Demaine,Erik D. / Demaine,Martin L. / Uehara,Ryuhei / Uno,Takeaki / Uno,Yushi)
　
8. 確率的評価値をもつゲーム木における最善手探索 (計算機科学とアルゴリズムの数理的基礎とその応用)------------------------------------56
　　　　九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学研究院 / 九州大学大学院システム情報科学研究院 / 九州大学大学院システム情報科学研究院　　　奥山 洋平 / 畑埜 晃平 / 瀧本 英二 / 竹田 正幸　(Okuyama,Yohei / Hatano,Kohei / Takimoto,Eiji / Takeda,Masayuki)
　
9. Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)---60
　　　　東北大学情報科学研究科 / JST / 電気通信大学情報システム学研究科 / 九州大学システム情報科学研究院 /北陸先端技術大学大学院教育イニシアティブセンター / 九州大学経済学研究科 / 大阪府立大学理学系 / 群馬大学工学研究科　　　大舘 陽太 / 斎藤 寿樹 / 山中 克久 / 来嶋 秀治 / 岡本 吉央 / 小野 廣隆 / 宇野 裕之 / 山崎 浩一　(Otachi,Yota / Saitoh,Toshiki / Yamanaka,Katsuhisa / Kijima,Shuji / Okamoto,Yoshio / Ono,Hirotaka / Uno,Yushi / Yamazaki,Koichi)
　
10. Approximating Maximum Edge 2-Coloring in Simple Graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)---67
　　　　東京電機大学理工学部情報システムデザイン学系 / 東京電機大学理工学研究科情報学専攻 / 東京電機大学理工学研究科情報学専攻　　　Chen Zhi-Zhong / 今野 さゆり / 松下 裕希　(Chen,Zhi-Zhong / Konno,Sayuri / Matsushita,Yuki)
　
11. Universality of Reversible Logic Elements with 1-Bit Memory : Extended Abstract (Mathematical Foundations and Applications of Computer Science and Algorithms)---77
　　　　広島大学工学研究科 /広島大学工学研究科 / 広島大学工学研究科 / 広島大学工学研究科　　　森田 憲一 / 荻路 剛 / Alhazov Artiom / 谷沢 剛　(Morita,Kenichi / Ogiro,Tsuyoshi / Alhazov,Artiom / Tanizawa,Tsuyoshi)
　
12. 2次の効用関数を持つ不可分財の最適配分問題に対する近似解法の研究 (計算機科学とアルゴリズムの数理的基礎とその応用)----------------85
　　　　東北大学大学院情報科学研究科 / 東北大学大学院情報科学研究科　　　鈴木 瞬也 / 塩浦 昭義　(Suzuki,Shunya / Shioura,Akiyoshi)
　
13. タブローの最適配置問題 (計算機科学とアルゴリズムの数理的基礎とその応用)---------------------------------------------------------93
　　　　東北大学大学院情報科学研究科 / 東北大学大学院情報科学研究科 / 東北大学大学院情報科学研究科 / ブリュセル自由大学 / 東北大学大学院情報科学研究科　　　安齋 進也 / 全 眞嬉 / 葛西 亮生 / コルマン マティアス / 徳山 豪　(Anzai,Shinya / Chun,Jinhee / Kasai,Ryosei / Korman,Matias / Tokuyama,Takeshi)
　
14. 組合せの効率的な生成法 (計算機科学とアルゴリズムの数理的基礎とその応用)---------------------------------------------------------99
　　　　京都大学大学院情報学研究科数理工学専攻 / 京都大学大学院情報学研究科数理工学専攻 / 京都大学大学院情報学研究科数理工学専攻　　　清水 俊宏 / 福永 拓郎 / 永持 仁　(Shimizu,Toshihiro / Fukunaga,Takuro / Nagamochi,Hiroshi)
　
15. 最長共通部分配列計算における run 長の対数時間寄与 (計算機科学とアルゴリズムの数理的基礎とその応用)-----------------------------107
　　　　東北大学大学院農学研究科　　　酒井 義文　(Sakai,Yoshifumi)
　
16. A Searchable Compressed Edit-Sensitive Parsing (Mathematical Foundations and Applications of Computer Science and Algorithms)---115
　　　　九州工業大学情報工学研究科 / 九州工業大学情報工学研究科 / 九州大学システム情報科学研究科 / 九州工業大学情報工学研究科・JST PRESTO　　　岸上 直也 / 中原 昌也 / 丸山 史郎 / 坂本 比呂志　(Kishiue,Naoya / Nakahara,Masaya / Maruyama,Shirou / Sakamoto,Hiroshi)
　
17. 圧縮文字列上での $q$-gram 頻度の高速な計算方法 (計算機科学とアルゴリズムの数理的基礎とその応用)--------------------------------123
　　　　九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学研究院 / 九州大学大学院システム情報科学研究院 / 九州大学大学院システム情報科学研究院　　　後藤 啓介 / 坂内 英夫 / 稲永 俊介 / 竹田 正幸　(Goto,Keisuke / Bannai,Hideo / Inenaga,Shunsuke / Takeda,Masayuki)
　
18. Dynamic Programming Algorithm for Optimal Double-Base Chains : Extended Abstract (Mathematical Foundations and Applications of Computer Science and Algorithms)---129
　　　　東京大学情報理工学系・JST / NEC Corp.・東京大学情報理工学系 / 東京大学情報理工学系・JST　　　Suppakitpaisarn Vorapong / 枝廣 正人 / 今井 浩　(Suppakitpaisarn,Vorapong / Edahiro,Masato / Imai,Hiroshi)
　
19. Local Composition of Cellular Automata via Hit-or-Miss Transform (Mathematical Foundations and Applications of Computer Science and Algorithms)---137
　　　　九州工業大学情報工学研究科　　　藤尾 光彦　(Fujio,Mitsuhiko)
　
20. Cancel minimal linear grammars with a particular nonterminal symbol (Mathematical Foundations and Applications of Computer Science and Algorithms)---144
　　　　九州大学研究戦略企画室 / 東京電機大学理工学部　　　藤岡 薫 / 勝野 裕文　(Fujioka,Kaoru / Katsuno,Hirofumi)
　
21. Degree sequences related to degree set : extended abstract (Mathematical Foundations and Applications of Computer Science and Algorithms)---151
　　　　群馬大学工学研究科 / 群馬大学工学研究科　　　大澤 新吾 / 柴田 幸夫　(Osawa,Shingo / Shibata,Yukio)
　
22. いかなる辺展開でも正多面体は重なりを持たない (計算機科学とアルゴリズムの数理的基礎とその応用)----------------------------------159
　　　　埼玉大学理工学研究科 / 埼玉大学理工学研究科　　　堀山 貴史 / 庄子 亘　(Horiyama,Takashi / Shoji,Wataru)
　
23. 木オートマトンを用いた化学グラフのスクリーニング手法 (計算機科学とアルゴリズムの数理的基礎とその応用)--------------------------161
　　　　茨城大学工学部情報工学科　　　藤芳 明生　(Fujiyoshi,Akio)
　
24. 最大クリーク問題の多項式時間的可解性について (計算機科学とアルゴリズムの数理的基礎とその応用)----------------------------------169
　　　　電気通信大学先進アルゴリズム研究ステーション / 電気通信大学先進アルゴリズム研究ステーション・中央大学研究開発機構 / 電気通信大学先進アルゴリズム研究ステーション・電気通信大学情報理工学研究科 / 電気通信大学先進アルゴリズム研究ステーション・電気通信大学情報理工学研究科　　　中西 裕陽 / 富田 悦次 / 若月 光夫 / 西野 哲朗　(Nakanishi,Hiroaki / Tomita,Etsuji / Wakatsuki,Mitsuo / Nishino,Tetsuro)
　
25. 最急上昇法による尾根抽出 (計算機科学とアルゴリズムの数理的基礎とその応用)------------------------------------------------------177
　　　　日本大学文理学部 / 日本大学文理学部 / 東海大学理学部 / 東洋大学工学部 / 日本大学文理学部　　　高加 晋司 / 野牧 賢志 / 杉田 公生 / 土田 賢省 / 夜久 竹夫　(Koka,Shinji / Nomaki,Kenshi / Sugita,Kimio / Tsuchida,Kensei / Yaku,Takeo)
　
26. 量子セルオートマトンに基づく画像圧縮のための画像変換アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)--------------181
　　　　電気通信大学大学院情報理工学研究科 / 電気通信大学大学院情報理工学研究科 / 電気通信大学大学院情報理工学研究科　　　大畑 和樹 / 西野 哲朗 / 若月 光夫　(Oohata,Kazuki / Nishino,Tetsuro / Wakatsuki,Mitsuo)
　
27. Image Recognition and Retrieval by Using Distance Information (Mathematical Foundations and Applications of Computer Science and Algorithms)---185
　　　　東北大学情報科学研究科 / 東北大学情報科学研究科 / 東北大学情報科学研究科　　　全 眞嬉 / Kaothanthong Natsuda / 徳山 豪　(Chun,Jinhee / Kaothanthong,Natsuda / Tokuyama,Takeshi)
　
28. AKS 素数判定アルゴリズムについての計算機を用いた実験的考察 (計算機科学とアルゴリズムの数理的基礎とその応用)--------------------189
　　　　岡山大学大学院自然科学研究科 / 岡山大学大学院自然科学研究科　　　難波 雄策 / 神保 秀司　(NANBA,Yusaku / JIMBO,Shuji)
　
29. 線形刻み幅の双対定理について (計算機科学とアルゴリズムの数理的基礎とその応用)--------------------------------------------------193
　　　　群馬大学工学研究科情報工学専攻 / 群馬大学工学研究科情報工学専攻 / 群馬大学工学研究科情報工学専攻 / 東北大学大学院情報科学研究科システム情報科学専攻 / 群馬大学工学研究科情報工学専攻　　　片平 明 / 桑原 勇人 / 長澤 亮介 / 大舘 陽太 / 山崎 浩一　(Katahira,Akira / Kuwabara,Yuto / Nagasawa,Ryosuke / Otachi,Yota / Yamazaki,Koichi)
　
30. 非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)--------197
　　　　九州大学システム情報科学研究院 / 九州大学大学院経済学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　藤永 直 / 小野 廣隆 / 来嶋 秀治 / 山下 雅史　(Fujinaga,Nao / Ono,Hirotaka / Kijima,Shuji / Yamashita,Masafumi)
　
31. 大規模分散フレームワーク Hadoop を用いた接尾辞配列構築 (計算機科学とアルゴリズムの数理的基礎とその応用)------------------------201
　　　　九州大学システム情報科学府 / 国立情報学研究所 / 九州大学大学院システム情報科学研究院　　　田中 洋輔 / 定兼 邦彦 / 山下 雅史　(Tanaka,Yosuke / Sadakane,Kunihiko / Yamashita,Masafumi)
　
32. ストリーミング中の頻出アイテム発見アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)--------------------------------205
　　　　九州大学システム情報科学府 / 九州大学システム情報科学府 / 九州大学システム情報科学府　　　緒方 正虎 / 来嶋 秀治 / 山下 雅史　(Ogata,Masatora / Kijima,Shuji / Yamashita,Masafumi)
　
33. 文法圧縮に基づいた圧縮データの自己索引構造化の提案 (計算機科学とアルゴリズムの数理的基礎とその応用)----------------------------209
　　　　九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学研究院 / 九州工業大学大学院情報工学研究院 / 国立情報学研究所 / 九州大学大学院システム情報科学研究院　　　馬場 雅大 / 丸山 史郎 / 坂本 比呂志 / 定兼 邦彦 / 山下 雅史　(Baba,Masahiro / Maruyama,Shirou / Sakamoto,Hiroshi / Sadakane,Kunihiko / Yamashita,Masafumi)
　
34. センサネットワーク上の群生成による情報伝達 (計算機科学とアルゴリズムの数理的基礎とその応用)------------------------------------213
　　　　東京電機大学工学研究科 / 東京電機大学工学研究科 / 広島大学工学研究科　　　中山 彈作 / 坂本 直志 / 今井 克暢　(Nakayama,Dansaku / Sakamoto,Naoshi / Imai,Katsunobu)
　
35. 仮想世界上での近距離合意問題 (計算機科学とアルゴリズムの数理的基礎とその応用)--------------------------------------------------217
　　　　東京電機大学大学院工学研究科　　　榎本 慎太郎　(Enomoto,Shintaro)