No.1554
計算機科学の理論とその応用
Theory of Computer Science and Its Applications
RIMS 研究集会報告集
 　
2007/01/29〜2007/01/31
中野　浩嗣
Koji Nakano
　
目　次
　
1. 時間付き$\pi$計算における有限プロセスの時間動作抽象化(計算機科学の理論とその応用)-------------------------------------------------1
　　　　立命館大学情報理工学部 / 名古屋大学大学院情報科学研究科 / 名古屋大学大学院情報科学研究科　　　桑原 寛明 / 結縁 祥治 / 阿草 清滋
　
2. Alternating CFG の拡張について(計算機科学の理論とその応用)------------------------------------------------------------------------9
　　　　早稲田大学教育学部 / /　　　守屋 悦朗 / /　(Moriya, Etsuro / Otto, Friedrich / Messerschmidt, Hartmut)
　
3. Neighborhood Function for CA(Theory of Computer Science and Its Applications)----------------------------------------------------16
　　　　(元)京都大学理学部 / カールスルーエ大学情報工学部　　　西尾 英之助 / ヴォルシュ トーマス　(Nishio, Hidenosuke / Worsch, Thomas)
　
4. Variations on Neighborhoods in CA(Theory of Computer Science and Its Applications)-----------------------------------------------24
　　　　カールスルーエ大学情報工学部 / (元)京都大学理学部　　　ヴォルシュ トーマス / 西尾 英之助　(Worsch, Thomas / Nishio, Hidenosuke)
　
5. 三部符号及び三部符号形式による RSA 暗号系(計算機科学の理論とその応用)------------------------------------------------------------32
　　　　岡山大学大学院自然科学研究科 / 岡山大学大学院自然科学研究科 / 岡山大学大学院自然科学研究科　　　丁 峰 / 神保 秀司 / 橋口 攻三郎　(Ding, Feng / Jimbo, Shuji / Hashiguchi, Kosaburo)
　
6. A Lattice-Based Cryptosystem and Proof of Knowledge on Its Secret Key(Theory of Computer Science and Its Applications)-----------40
　　　　Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology / Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology / Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology　　　草川 恵太 / 河内 亮周 / 田中 圭介　(Xagawa, Keita / Kawachi, Akinori / Tanaka, Keisuke)
　
7. 集合被覆問題に関する近似アルゴリズムの秘匿性(計算機科学の理論とその応用)---------------------------------------------------------48
　　　　東京工業大学数理計算科学専攻 / 東京工業大学数理計算科学専攻　　　八代 正俊 / 田中 圭介　(Yashiro, Masatoshi / Tanaka, Keisuke)
　
8. アメリカン・アジアンオプションの価格付けに対する計算幾何手法を用いた近似アルゴリズム(計算機科学の理論とその応用)-----------------56
　　　　東北大学大学院情報科学研究科 / 東北大学大学院情報科学研究科 / 東北大学大学院情報科学研究科　　　渋谷 彰信 / 塩浦 昭義 / 徳山 豪　(Shibuya, Akinobu / Shioura, Akiyoshi / Tokuyama, Takeshi)
　
9. 根付きサイクル被覆問題に対する近似最適解法(計算機科学の理論とその応用)-----------------------------------------------------------64
　　　　東北大学大学院情報科学研究科　　　羽田 明生
　
10. Approximation Algorithm for Maximum Triangle Packing and Metric Maximum Clustering(Theory of Computer Science and Its Applications)---71
　　　　Graduate School of Science and Engineering, Tokyo Denki University / Graduate School of Science and Engineering, Tokyo Denki University / Graduate School of Science and Engineering, Tokyo Denki University　　　CHEN, Zhi-Zhong / Tanahashi, Ruka / Sekiyama, Tatsuyuki
　
11. An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graph(Theory of Computer Science and Its Applications)---78
　　　　Graduate School of Science and Engineering, Tokyo Denki University / Graduate School of Science and Engineering, Tokyo Denki University　　　CHEN, Zhi-Zhong / Tanahashi, Ruka
　
12. Orthogonal Drawings for Plane Graphs with Specified Face Areas(Theory of Computer Science and Its Applications)-----------------85
　　　　Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University / Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University　　　Kawaguchi, Akifumi / Nagamochi, Hiroshi
　
13. 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)-------------------------------------------------93
　　　　北陸先端科学技術大学院大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科　　　斎藤 寿樹 / 清見 礼 / 上原 隆平
　
14. 負荷分散枝被覆問題に対する最適性とアルゴリズム(計算機科学の理論とその応用)-----------------------------------------------------101
　　　　九州大学大学院システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　原田 雄太 / 小野 廣隆 / 定兼 邦彦[他]
　
15. Ptolemaic Graph 上の最長路問題に関する研究(計算機科学の理論とその応用)---------------------------------------------------------109
　　　　北陸先端科学技術大学院大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科　　　高原 祥浩 / 寺本 幸生 / 上原 隆平　(Takahara, Yoshihiro / Teramoto, Sachio / Uehara, Ryuhei)
　
16. Quantum Asymmetric-Key Cryptosystems Secure Against Computationally Unbounded Adversaries(Theory of Computer Science and Its Applications)---117
　　　　Department of Mathematical and Computing Sciences, Tokyo Institute of Technology / Department of Mathematical and Computing Sciences, Tokyo Institute of Technology　　　Kawachi, Akinori / Portmann, Christopher
　
17. 量子回路計算量と制御 NOT ゲート数の関係について(計算機科学の理論とその応用)----------------------------------------------------125
　　　　電気通信大学大学院情報通信工学専攻 / 電気通信大学大学院情報通信工学専攻 / 電気通信大学大学院情報通信工学専攻　　　大久保 誠也 / 青木 輝人 / 柿下 容弓[他]
　
18. Negation-Limited Complexity of Parity and Inverters(Theory of Computer Science and Its Applications)---------------------------131
　　　　京都大学大学院情報学研究科 / 電気通信大学情報通信工学科 / 京都大学大学院情報学研究科　　　森住 大樹 / 垂井 淳 / 岩間 一雄
　
19. 境界上を移動可能なロボット2台による多角形探索(計算機科学の理論とその応用)------------------------------------------------------139
　　　　九州大学大学院システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　深見 浩和 / 小野 廣隆 / 定兼 邦彦[他]
　
20. 3正則グラフの巡回セールスマン問題に対する厳密アルゴリズムの改善(計算機科学の理論とその応用)------------------------------------145
　　　　京都大学情報学研究科 / 京都大学情報学研究科　　　岩間 一雄 / 中島 拓也　(Iwama, Kazuo / Nakashima, Takuya)
　
21. A Fast Algorithm for Computing Jones Polynomials of Montesinos Links(Theory of Computer Science and Its Applications)----------153
　　　　Graduate School of Integrated Basic Sciences, Nihon University / Department of Mathematical Sciences, Tokai University / Department of Mathematics, Chuo University　　　Murakami, Masahiko / Hara, Masao / Yamamoto, Makoto[他]
　
22. Direct Binary Search 法によるマルチトニング(計算機科学の理論とその応用)--------------------------------------------------------161
　　　　広島大学大学院工学研究科 / 広島大学大学院工学研究科　　　平野 祐樹 / 中野 浩嗣
　
23. Decidability of Innermost Termination for Semi-Constructor Term Rewriting Systems(Theory of Computer Science and Its Applications)---166
　　　　School of Engineering, Nagoya University / Graduate School of Information Science, Nagoya University / Graduate School of Information Science, Nagoya University　　　Uchiyama, Keita / Sakai, Masahiro / Nishida, Naoki[他]
　
24. Confluence of Length Preserving String Rewriting Systems is Undecidable(Theory of Computer Science and Its Applications)-------171
　　　　Graduate School of Information Science, Nagoya University / Graduate School of Information Science, Nagoya University / Graduate School of Information Science, Nagoya University　　　Wang, Yi / Sakai, Masahiko / Nishida, Naoki[他]
　
25. 単純型付き等式系に基づく定理自動証明に関する一考察(計算機科学の理論とその応用)-------------------------------------------------178
　　　　三重大学大学院工学研究科情報工学専攻 / 三重大学大学院工学研究科情報工学専攻 / 三重大学大学院工学研究科情報工学専攻　　　岡村 洋 / 大山口 通夫 / 山田 俊行
　
26. 価値関数によるソフトリアルタイムシステムのスケジューラ自動合成手法(計算機科学の理論とその応用)---------------------------------186
　　　　金沢大学自然科学研究科 / 金沢大学自然科学研究科　　　加納 卓 / 山根 智　(Kano, Suguru / Yamane, Satoshi)
　
27. 述語抽象化洗練を用いたリアルタイムプログラムの自動検証手法(計算機科学の理論とその応用)-----------------------------------------194
　　　　金沢大学大学院自然科学研究科電子情報工学専攻 / 金沢大学大学院自然科学研究科電子情報工学専攻　　　駒形 龍太 / 山根 智　(Komagata, Ryota / Yamane, Satoshi)
　
28. 確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察(計算機科学の理論とその応用)---------------------------202
　　　　Department of Computer Science and Communication Engineering, Kyushu University / Department of Computer Science and Communication Engineering, Kyushu University / Graduate School of Information Science and Electrical Engineering, Kyushu University　　　安藤 映 / 小野 廣隆 / 定兼 邦彦[他]　(Ando, Ei / Ono, Hirotaka / Sadakane, Kunihiko)
　
29. DAG の高さを4以下に制限したタスクスケジューリングの近似アルゴリズムについて(計算機科学の理論とその応用)------------------------210
　　　　三重大学工学部 / 三重大学工学部 / 三重大学工学部　　　清水 豪樹 / 大山口 通夫 / 山田 俊行[他]　(SHIMIZU, Kouki / OYAMAGUCHI, Michio / YAMADA, Toshiyuki)
　
30. 定数項の大きな線形しきい値関数に対する高速なオンライン学習(計算機科学の理論とその応用)-----------------------------------------217
　　　　九州大学システム情報科学研究院情報理学部門 / 九州大学システム情報科学研究院情報理学部門 / 九州大学システム情報科学研究院情報理学部門　　　石橋 浩介 / 畑埜 晃平 / 竹田 正幸　(Ishibashi, Kosuke / Hatano, Kohei / Takeda, Masayuki)
　
31. 完全2分木に対するPath Distance Width の下界(計算機科学の理論とその応用)--------------------------------------------------------225
　　　　群馬大学工学部工学研究科 / 群馬大学工学部工学研究科 / 群馬大学工学部工学研究科　　　受川 和幸 / 青木 一正 / 大舘 陽太[他]　(Ukegawa, K. / Aoki, K. / Otachi, Y.)
　
32. Branch-length とtree-length(計算機科学の理論とその応用)------------------------------------------------------------------------230
　　　　群馬大学大学院工学研究科 / 群馬大学工学部情報工学科　　　梅澤 香織 / 山崎 浩一　(Umezawa, K. / Yamazaki, K.)
　
33. ボトムアップ手法を用いた系統樹構築の近似アルゴリズム(計算機科学の理論とその応用)-----------------------------------------------238
　　　　九州大学大学院システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　前村 一哉 / 小野 廣隆 / 定兼 邦彦[他]　(Maemura, Kazuya / Ono, Hirotaka / Sadakane, Kunihiko)
　
34. 部分文字列の高速復元に適した圧縮データ構造に関する研究(計算機科学の理論とその応用)---------------------------------------------243
　　　　九州大学大学院システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　後藤 隆元 / 小野 廣隆 / 定兼 邦彦[他]　(Goto, Takamoto / Ono, Hirotaka / Sadakane, Kunihiko)
　
35. 局所探索法に基づくDNA 配列設計手法(計算機科学の理論とその応用)-----------------------------------------------------------------250
　　　　九州大学大学院システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　川下 優 / 小野 廣隆 / 定兼 邦彦[他]
　
36. $K$- 開発閉包な左線形項書換えシステムの合流性(計算機科学の理論とその応用)------------------------------------------------------258
　　　　島根大学総合理工学部　　　岩見 宗弘　(Iwami, Munehiro)
　
37. センサーネットワークにおける省電力高信頼なデータ伝送(計算機科学の理論とその応用)-----------------------------------------------264
　　　　九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学府　　　佐薙 光樹 / 小野 廣隆 / 定兼 邦彦[他]　(Sanagi, Koki / Ono, Hirotaka / Sadakane, Kunihiko)
　
38. $k$-Set Agreement を解く故障検知器(計算機科学の理論とその応用)-----------------------------------------------------------------269
　　　　九州大学大学院システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　坂田 敦 / 小野 廣隆 / 定兼 邦彦[他]　(Sakata, Atsushi / Ono, Hirotaka / Sadakane, Kunihiko)
　
39. 信用交渉における公開木戦略の計算量(計算機科学の理論とその応用)-----------------------------------------------------------------276
　　　　奈良先端科学技術大学院大学情報科学研究科 / 奈良先端科学技術大学院大学情報科学研究科 / 奈良先端科学技術大学院大学情報科学研究科　　　山本 有輝 / 高田 喜朗 / 関 浩之