No.1426
計算機科学基礎理論とその応用
Theoretical Computer Science and its Applications
研究集会報告集
 　
2005/01/31〜2005/02/02
谷口　健一
Kenichi Taniguchi　
　
目　次
　
1. Improved Deterministic Approximation Algorithms for Max TSP (Theoretical Computer Science and its Applications)-------------------1
　　　　東京電機大学理工学部数理科学科 / 東京電機大学理工学部数理科学科 / 香港城市大学計算機系　　　陳 致中 / 岡本 裕介 / 王 魯生　(Chen, Zhi-Zhong / Okamoto, Yuusuke / Wang, Lusheng)
　
2. An Improved Randomized Approximation Algorithm for Max TSP (Theoretical Computer Science and its Applications)--------------------7
　　　　東京電機大学理工学部数理科学科 / 香港城市大学計算機系　　　陳 致中 / 王 魯生　(Chen, Zhi-Zhong / Wang, Lusheng)
　
3. Hajos Calculus on Planar Graphs (Theoretical Computer Science and its Applications)----------------------------------------------13
　　　　京都大学情報学研究科 / 京都大学情報学研究科 / 京都大学情報学研究科　　　花谷 陽一 / 堀山 貴史 / 岩間 一雄　(Hanatani, Yoichi / Horiyama, Takashi / Iwama, Kazuo)
　
4. A Hierarchy of Tree Edit Distance Measures (Theoretical Computer Science and its Applications)-----------------------------------20
　　　　東京大学国際・産学共同研究センター / 東京大学先端科学技術センター / 広島市立大学情報科学部　　　久保山 哲二 / 申 吉浩 / 宮原 哲浩　(Kuboyama, Tetsuji / Shin, Kilho / Miyahara, Tetsuhiro)
　
5. 構文解析木の類似度の判定アルゴリズム (計算機科学基礎理論とその応用)--------------------------------------------------------------26
　　　　岡山理科大学総合情報学部 / 岡山理科大学総合情報学部　　　椎名 広光 / 秋友 克俊　(Shiina, Hiromitsu / Akitomo, Katsutoshi)
　
6. $O(n^3)$で認識される文脈自由木言語のサブクラスについて (計算機科学基礎理論とその応用)--------------------------------------------32
　　　　電気通信大学電気通信学研究科 / 茨城大学工学部情報工学科　　　川原田 郁雄 / 藤芳 明生　(Kawaharada, Ikuo / Fujiyoshi, Akio)
　
7. 配列を扱う非線形先頭再帰プログラムからの再帰除去 (計算機科学基礎理論とその応用)--------------------------------------------------39
　　　　名古屋大学工学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科　　　高須 洋平 / 酒井 正彦 / 西田 直樹 / 草刈 圭一朗 / 坂部 俊樹　(Takasu, Yohei / Sakai, Masahiko / Nishida, Naoki / Kusakari, Keiichirou / Sakabe, Toshiki)
　
8. 正規パターン言語の和と共通部分の帰納学習 (計算機科学基礎理論とその応用)----------------------------------------------------------45
　　　　大阪府立大学総合科学部　　　植村 仁　(Uemura, Jin)
　
9. ランキング関数のオンライン学習について (計算機科学基礎理論とその応用)------------------------------------------------------------51
　　　　北海道大学情報科学研究科　　　中村 篤祥　(Nakamura, Atsuyoshi)
　
10. 中程度の難しさをもつ関数のモデルと方式 (計算機科学基礎理論とその応用)-----------------------------------------------------------57
　　　　東京工業大学数理・計算科学専攻 /東京工業大学数理・計算科学専攻　　　小野寺 貴男 / 田中 圭介　(Onodera, Takao / Tanaka, Keisuke)
　
11. Sampling Twiceテクニックと匿名性をもつRSA暗号方式 (計算機科学基礎理論とその応用)------------------------------------------------64
　　　　東京工業大学数理・計算科学専攻 / 東京工業大学数理・計算科学専攻　　　林 良太郎 / 田中 圭介　(Hayashi, Ryotaro / Tanaka, Keisuke)
　
12. On NK-Community Problem (Theoretical Computer Science and its Applications)-----------------------------------------------------71
　　　　北海道大学情報科学研究科 / 東京工業大学情報理工学研究科 / 東京工業大学情報理工学研究科　　　中村 篤祥 / 繁住 健哉 / 山本 真基　(Nakamura, Atsuyoshi / Shigezumi, Takeya / Yamamoto, Masaki)
　
13. モバイルエージェント実行計画問題について (計算機科学基礎理論とその応用)---------------------------------------------------------78
　　　　日本電信電話株式会社NTTコミュニケーション科学基礎研究所 / 豊橋技術科学大学知識情報工学系 / 日本電信電話株式会社NTTコミュニケーション科学基礎研究所 / 豊橋技術科学大学知識情報工学系　　　佐々木 淳 / 宮田 敬三 / 櫟 粛之 / 増山 繁　(Sasaki, Atsushi / Miyata, Keizo / Arargi [Araragi], Tadashi / Masuyama, Shigeru)
　
14. 進化的ネットワークにおける探索アルゴリズムの提案 (計算機科学基礎理論とその応用)-------------------------------------------------84
　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　緒方 司 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Ogata, Tsukasa / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)
　
15. 部分IDの一意性を考慮したID集合生成に関する問題 (計算機科学基礎理論とその応用)---------------------------------------------------91
　　　　九州大学システム情報科学府情報工学専攻 / 九州大学システムLSI研究センター / 九州大学システムLSI研究センター　　　牧山 幸史 / 納富 貞嘉 / 安浦 寛人　(Makiyama, Koji / Noutomi, Sadayoshi / Yasuura, Hiroto)
　
16. An Energy Complexity Measure for Threshold Circuits that is Motivated by Biological Data on Cortical Computations (Theoretical Computer Science and its Applications)---96
　　　　東北大学情報科学研究科　　　内沢 啓　(Uchizawa, Kei)
　
17. The Reachability and Related Decision Problems for Semi-Constructor TRSs (Theoretical Computer Science and its Applications)---101
　　　　三重大学工学部 / 三重大学工学部 / 三重大学工学部　　　三橋 一郎 / 大山口 通夫 / 山田 俊行　(Mitsuhashi, Ichiro / Oyamaguchi, Michio / Yamada, Toshiyuki)
　
18. 項到達可能性の判定における成長TRSに対する手法と正規化規則による手法の関係 (計算機科学基礎理論とその応用)-----------------------106
　　　　名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科　　　村田 龍彦 / 酒井 正彦 / 西田 直樹 / 草刈 圭一朗 / 坂部 俊樹　(Murata, Tatsuhiko / Sakai, Masahiko / Nishida Naoki / Kusakari, Keiichirou / Sakabe, Toshiki)
　
19. 変換と部分評価に基づく非左辺正規なメタ項の停止性証明 (計算機科学基礎理論とその応用)--------------------------------------------113
　　　　名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科　　　蛸島 洋明 / 酒井 正彦 / 坂部 俊樹 / 西田 直樹 / 草刈 圭一朗　(Takojima, Hiroaki / Sakai, Masahiko / Sakabe, Toshiki / Nishida, Naoki / Kusakari, Keiichirou)
　
20. 弱最内戦略を完全にする項書換え系の等価変換 (計算機科学基礎理論とその応用)------------------------------------------------------119
　　　　名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科　　　岡本 晃治 / 酒井 正彦 / 西田 直樹 / 草刈 圭一朗 / 坂部 俊樹　(Okamoto, Koji / Sakai, Masahiko / Nishida, Naoki / Kusakari, Keiichirou / Sakabe, Toshiki)
　
21. An Improved Recursive Decomposition Ordering for Term Rewriting Systems Revisited (Theoretical Computer Science and its Applications)---126
　　　　島根大学総合理工学部　　　岩見 宗弘　(Iwami, Munehiro)
　
22. 確率時間オートマトンの確率時間強模倣検証アルゴリズム (計算機科学基礎理論とその応用)--------------------------------------------133
　　　　金沢大学自然科学研究科 / 金沢大学自然科学研究科　　　小寺 広志 / 山根 智　(Kodera, Hiroshi / Yamane, Satoshi)
　
23. Hausdorff Dimension and the Stochastic Traveling Salesman Problem (Theoretical Computer Science and its Applications)----------140
　　　　東京工業大学情報理工学研究科数理・計算科学専攻　　　高橋 勇人　(Takahashi, Hayato)
　
24. 一般化ぷよぷよのNP完全性 (計算機科学基礎理論とその応用)------------------------------------------------------------------------147
　　　　電気通信大学 / 電気通信大学　　　松金 輝久 / 武永 康彦　(Matsukane, Teruhisa / Takenaga, Yasuhiko)
　
25. 比較可能+keグラフの彩色問題 (計算機科学基礎理論とその応用)---------------------------------------------------------------------153
　　　　電気通信大学 / 電気通信大学　　　東出 賢一 / 武永 康彦　(Higashide, Kenichi / Takenaga, Yasuhiko)
　
26. Perfectness and Multicoloring of Unit Disk Graphs on Triangular Lattice Points (Theoretical Computer Science and its Applications)---159
　　　　上智大学理工学部 / 東京大学情報理工学系研究科　　　宮本 裕一郎 / 松井 知己　(Miyamoto, Yuichiro / Matsui, Tomomi)
　
27. An approximation algorithm for matroid covering (Theoretical Computer Science and its Applications)----------------------------166
　　　　群馬大学工学部情報工学科 / 群馬大学工学部情報工学科 / 群馬大学工学部情報工学科　　　川野 晋一郎 / 大舘 陽太 / 山崎 浩一　(Kawano, Shinichiro / Otachi, Yota / Yamazaki, Koichi)
　
28. Generating Monotone Trees : Extended Abstract (Theoretical Computer Science and its Applications)------------------------------172
　　　　秋田県立大学システム科学技術学部電子情報システム学科 / 秋田県立大学システム科学技術研究科電子情報システム学専攻 / 秋田県立大学システム科学技術学部電子情報システム学科 / 秋田県立大学システム科学技術学部電子情報システム学科　　　草苅 良至 / 新里 善美 / 能登谷 淳一 / 笠井 雅夫　(Kusakari, Yoshiyuki / Niisato, Yoshimi / Notoya, Jyunichi / Kasai, Masao)
　
29. 2-リンクパズルの多項式時間解法 (計算機科学基礎理論とその応用)------------------------------------------------------------------178
　　　　東京工業大学理学部情報科学科　　　牧野 格三　(Makino, Kozo)
　
30. 最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論とその応用)----------------184
　　　　三重大学工学部 / 三重大学工学部 / 三重大学工学部 / 三重大学工学部　　　新美 信之助 / 大山口 通夫 / 太田 義勝 / 山本 浩平　(Niimi, Shinnosuke / Oyamaguchi, Michio / Ohta, Yoshikatsu / Yamamoto, Kohei)
　
31. 文字列のシフトにより得られるダイグラフについて (計算機科学基礎理論とその応用)--------------------------------------------------189
　　　　群馬大学工学部情報工学科 / 群馬大学工学部情報工学科　　　田中 勇樹 / 柴田 幸夫　(Tanaka, Yuuki / Shibata, Yukio)
　
32. 3近傍可逆セルオートマトンについて (計算機科学基礎理論とその応用)---------------------------------------------------------------194
　　　　九州大学システム情報科学府 / 九州大学システム情報科学府 / 九州大学数理学研究院 / 大分工業高等専門学校 / 九州大学システム情報科学研究院　　　川原 敬弘 / 本多 和正 / 井口 修一 / 佐藤 達郎 / 河原 康雄　(Kawahara, Takahiro / Honda, Kazumasa / Inokuchi, Shuichi / Sato, Tatsuro / Kawahara, Yasuo)
　
33. 万能可逆チューリング機械の一構成法 (計算機科学基礎理論とその応用)--------------------------------------------------------------200
　　　　広島大学工学研究科 / 広島大学工学研究科　　　安部 崇嗣 / 森田 憲一　(Abe, Takashi / Morita, Kenichi)
　
34. ファクターオラクルの誤受理構造の解析 (計算機科学基礎理論とその応用)------------------------------------------------------------206
　　　　東京工業大学理学部情報科学科　　　岩崎 久史　(Iwasaki, Hisashi)
　
35. Chaitin's halting probability $\Omega$ and quantum measurements in an infinite dimensional quantum system (Theoretical Computer Science and its Applications)---212
　　　　中央大学21世紀COEプログラム　　　只木 孝太郎　(Tadaki, Kohtaro)
　
36. Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications)------------------------219
　　　　今井量子計算機構プロジェクト(ERATO) / 東京工業大学情報理工学研究科 / 今井量子計算機構プロジェクト(ERATO) / 奈良先端科学技術大学院大学　　　岩間 一雄 / 河内 亮周 / / 山下 茂　(Iwama, Kazuo / Kawachi, Akinori / Raymond, Rudy / Yamashita, Shigeru)
　
37. 量子アルゴリズムによる近似文字列出現頻度問い合わせ (計算機科学基礎理論とその応用)----------------------------------------------225
　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　小林 健了 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Kobayashi, Takenori / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)
　
38. 分子構造変化のモデル化と反応速度の理論的解析 (計算機科学基礎理論とその応用)----------------------------------------------------232
　　　　九州大学システム情報科学府 / 九州大学システム情報科研究院 / 九州大学システム情報科研究院 / 九州大学システム情報科研究院　　　塩崎 真史 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Shiozaki, Masashi / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)
　
39. DNA形態変化におけるエネルギー障壁値の高速近似計算 (計算機科学基礎理論とその応用)-----------------------------------------------238
　　　　九州大学システム情報科学府情報工学専攻 / 九州大学システム情報科研究院情報工学部門 / 九州大学システム情報科研究院情報工学部門 / 九州大学システム情報科研究院情報工学部門　　　武田 勉 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Takeda, Tsutomu / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)
　
40. 非同期セル空間における順序機械構成 (計算機科学基礎理論とその応用)--------------------------------------------------------------245
　　　　広島大学工学研究科 / 広島大学工学研究科　　　斉 金山 / 森田 憲一　(Qi, Jin-Shan / Morita, Kenichi)
　
41. 計算万能な双曲セル・オートマトンについて (計算機科学基礎理論とその応用)--------------------------------------------------------250
　　　　広島大学工学研究科 / 広島大学工学研究科 / 広島大学工学研究科　　　今井 克暢 / 岩本 宙造 / 森田 憲一　(Imai, Katsunobu / Iwamoto, Chuzo / Morita, Kenichi)
　
42. セルオートマトンの近傍系の代数的構造 (計算機科学基礎理論とその応用)------------------------------------------------------------256
　　　　京都大学理学研究科(元) / /　　　西尾 英之助 / マルゲンシュテルン モーリス / ヘーゼラー フリッツ・フォン　(Nishio, Hidenosuke / Margenstern, Maurice / Haeseler, Friedrich von)
　
43. パラメタ付き時間インターバルオートマトンに対するパラメトリック検証の高速化手法 (計算機科学基礎理論とその応用)------------------263
　　　　大阪大学情報科学研究科 / 大阪大学情報科学研究科 / 大阪大学情報科学研究科 / 大阪大学情報科学研究科　　　橋本 英明 / 谷本 匡亮 / 中田 明夫 / 東野 輝夫　(Hashimoto, Hideaki / Tanimoto, Tadaaki / Nakata, Akio / Higashino, Teruo)