No.1325

2003/02/03〜2003/02/05

富田　悦次, 西野　哲朗

Etsuji　Tomita, Tetsuro　Nishino

目　次

1. メタ戦略アルゴリズムに対するロバストな並列化 (計算機科学基礎理論の新展開)---------------------------------------------------------1

　　　　九州大学システム情報科学府/九州大学システム情報科学研究院/九州産業大学情報科学部社会情報システム学科/九州大学システム情報科学研究院　　　石橋 正裕/小野 廣隆/朝廣 雄一/山下 雅史　(Ishibashi, Masahiro/Ono, Hirotaka/Asahiro, Yuichi/Yamashita, Masafumi)

　

2. 守備特訓に喘ぐ外野手のための捕球経路問題 (計算機科学基礎理論の新展開)-------------------------------------------------------------8

　　　　九州大学システム情報科学研究院/九州大学システム情報科学研究院/九州大学システム情報科学研究院/九州産業大学情報科学部/大阪大学基礎工学研究科/京都大学情報学研究科　　　佐久間 俊慎/小野 廣隆/山下 雅史/朝廣 雄一/牧野 和久/堀山 貴史　(Sakuma, Toshinori/Ono, Hirotaka/Yamashita, Masafumi/Asahiro, Yuichi/Makino, Kazuhisa/Horiyama, Takashi)

　

3. 容量を制限した場合の移動物体巡回問題 (計算機科学基礎理論の新展開)----------------------------------------------------------------15

　　　　九州工業大学情報工学部制御システム工学科/九州産業大学情報科学部社会情報システム学科/九州工業大学情報工学部制御システム工学科　　　下入佐 真一/朝廣 雄一/宮野 英次　(Shimoirisa, Shinichi/Asahiro, Yuichi/Miyano, Eiji)

　

4. 短絡除去可能な順序なし二分木における最小被覆木問題に対する一考察 (計算機科学基礎理論の新展開)------------------------------------21

　　　　九州大学システム情報科学府情報工学部門/九州大学システム情報科学府情報工学部門　　　牧山 幸史/安浦 寛人　(Makiyama, Kouji/Yasuura, Hiroto)

　

5. 量子一方向性置換に基づく小さい保存領域のための量子ビットコミットメント (計算機科学基礎理論の新展開)------------------------------27

　　　　東京工業大学情報理工学研究科数理・計算科学専攻/東京工業大学情報理工学研究科数理・計算科学専攻　　　一色 寿幸/田中 圭介　(Isshiki, Toshiyuki/Tanaka, Keisuke)

　

6. Noise-Tolerant Quantum Oracles (New Aspects of Theoretical Computer Science)-----------------------------------------------------33

　　　　京都大学情報学研究科/京都大学情報学研究科　　　レイモンド・H・プテラ/岩間 一雄/山下 茂　(Putra, Raymond H./Iwama, Kazuo/Yamashita, Shigeru)

　

7. 節点重み最大クリーク抽出アルゴリズム (計算機科学基礎理論の新展開)----------------------------------------------------------------39

　　　　電気通信大学/電気通信大学/電気通信大学/電気通信大学　　　中村 知倫/富田 悦次/西野 哲朗/名久井 行秀　(Nakamura, Tomonori/Tomita, Etsuji/Nishino, Tetsuro/Nakui, Yukihide)

　

8. 節点重み最大クリーク抽出に基づく量子回路の深さ最小化 (計算機科学基礎理論の新展開)------------------------------------------------45

　　　　電気通信大学電気通信学研究科電子情報学専攻/電気通信大学電気通信学部情報通信工学科情報メディア工学講座/電気通信大学電気通信学部情報通信工学科情報メディア工学講座/電気通信大学電気通信学部情報通信工学科情報メディア工学講座　　　名久井 行秀/西野 哲朗/富田 悦次/中村 知倫　(Nakui, Yukihide/Nishino, Tetsuro/Tomita, Etsuji/Nakamura, Tomonori)

　

9. Recent Advancements of a Genetic Algorithm to Solve the Set Covering Problem (New Aspects of Theoretical Computer Science)-------51

　　　　城西大学理学部数学科/城西大学理学部数学科/城西大学理学部数学科　　　岩村 覚三/岡田 法雄/出口 洋三　(Iwamura, Kakuzo/Okada, Norio/Deguchi, Yozo)

　

10. A Highly Concurrent Algorithm for the Group Mutual Exclusion Problem (New Aspects of Theoretical Computer Science)--------------57

　　　　群馬大学工学部/群馬大学工学部　　　高村 政孝/五十嵐 善英　(Takamura, Masataka/Igarashi, Yoshihide)

　

11. 自然数の組成のO(1)時間生成について (計算機科学基礎理論の新展開)-----------------------------------------------------------------63

　　　　茨城大学総合情報処理センター/茨城大学工学部情報工学科　　　三河 賢治/仙波 一郎　(Mikawa, Kenji/Semba, Ichiro)

　

12. Polynomial Time Inductive Inference of Ordered Term Trees with Contractible Variables from Positive Data (New Aspects of Theoretical Computer Science)---69

　　　　九州大学システム情報科学府情報理学専攻/九州大学システム情報科学研究院情報理学部門/東海大学理学部情報数理学科/広島市立大学情報科学部/広島市立大学情報科学部　　　鈴木 祐介/正代 隆義/松本 哲志/内田 智之/宮原 哲浩　(Suzuki, Yusuke/Shoudai, Takayoshi/Matsumoto, Satoshi/Uchida, Tomoyuki/Miyahara, Tetsuhiro)

　

13. 間接結合ルールによるデータマイニング (計算機科学基礎理論の新展開)---------------------------------------------------------------75

　　　　大阪府立大学理学系研究科/大阪府立大学総合科学部数理・情報科学科　　　濱野 慎一/佐藤 優子　(Hamano, Shinichi/Sato, Masako)

　

14. 頻出順序木パターンを見つけるオンラインアルゴリズム (計算機科学基礎理論の新展開)-------------------------------------------------81

　　　　九州大学システム情報科学府・研究院/九州大学システム情報科学府・研究院/九州大学システム情報科学府・研究院/九州大学システム情報科学府・研究院/九州大学システム情報科学府・研究院　　　浅井 達哉/安部 賢治/川副 真治/有村 博紀/有川 節夫　(Asai, Tatsuya/Abe, Kenji/Kawasoe, Shinji/Arimura, Hiroki/Arikawa, Setsuo)

　

15. オンライン投資問題 (計算機科学基礎理論の新展開)---------------------------------------------------------------------------------87

　　　　名古屋大学情報文化学部自然情報学科/名古屋大学情報文化学部自然情報学科　　　築地 立家/横山 雄俊　(Tsukiji, Tatsuie/Yokoyama, Yushun)

　

16. 分解可能なしきい関数を用いたデータ解析 (計算機科学基礎理論の新展開)-------------------------------------------------------------93

　　　　九州大学システム情報科学府情報工学専攻/九州大学システム情報科学研究院情報工学部門/九州大学システム情報科学研究院情報工学部門　　　片岡 博幸/小野 廣隆/山下 雅史　(Kataoka, Hiroyuki/Ono, Hirotaka/Yamashita, Masafumi)

　

17. 協調型言語に基づく並列プロセスのモデル検証 (計算機科学基礎理論の新展開)---------------------------------------------------------98

　　　　愛媛大学理学部数理科学科　　　大塚 寛　(Ohtsuka, Hiroshi)

　

18. 再帰型をもつオブジェクト指向計算モデルにおける例外処理の型付 (計算機科学基礎理論の新展開)--------------------------------------104

　　　　名古屋大学工学研究科/名古屋大学工学研究科/名古屋大学工学研究科　　　堀江 美保子/酒井 正彦/坂部 俊樹　(Horie, Mihoko/Sakai, Masahiko/Sakabe, Toshiki)

　

19. 正規パターン言語の集合積の包合問題について (計算機科学基礎理論の新展開)--------------------------------------------------------110

　　　　四天王寺国際仏教大学/大阪府立大学総合科学部数理・情報科学科　　　寺田 幹治/佐藤 優子　(Terada, Mikiharu/Sato, Masako)

　

20. 2つの節をもつ正規基本形式体系の正例からの学習 (計算機科学基礎理論の新展開)-----------------------------------------------------116

　　　　大阪府立大学理学系研究科/大阪府立大学理学系研究科/大阪府立大学総合科学部数理・情報科学科　　　植村 仁/道正田 昌/佐藤 優子　(Uemura, Jin/Dosyouda, Masashi/Sato, Masako)

　

21. Polynomial Time Learnabilities of Tree Patterns with Internal Structured Variables from Queries (New Aspects of Theoretical Computer Science)---122

　　　　東海大学理学部情報数理学科/九州大学システム情報科学府情報理学専攻/九州大学システム情報科学研究院情報理学部門/広島市立大学情報科学部情報メディア工学科/広島市立大学情報科学部知能情報システム工学科　　　松本 哲志/鈴木 祐介/正代 隆義/内田 智之/宮原 哲浩　(Matsumoto, Satoshi/Suzuki, Yusuke/Shoudai, Takayoshi/Uchida, Tomoyuki/Miyahara, Tetsuhiro)

　

22. 別の数え上げ符号を用いたナップザック暗号 (計算機科学基礎理論の新展開)----------------------------------------------------------128

　　　　東京工業大学情報理工学研究科数理・計算科学専攻/東京工業大学情報理工学研究科数理・計算科学専攻　　　大村 慶二/田中 圭介　(Oomura, Keiji/Tanaka, Keisuke)

　

23. Short Exponent DDH (New Aspects of Theoretical Computer Science)---------------------------------------------------------------134

　　　　富士通研究所・セキュアコンピューティング研究部/茨城大学工学部情報工学科　　　小柴 健史/黒澤 馨　(Koshiba, Takeshi/Kurosawa, Kaoru)

　

24. DNA計算における部分グラフ同型問題の解法について (計算機科学基礎理論の新展開)---------------------------------------------------140

　　　　名古屋工業大学/名古屋工業大学/名古屋工業大学/名古屋工業大学/名古屋工業大学//名古屋工業大学　　　片山 貴晴/鵜飼 亮介/五所野尾 一彦/伊藤 暢浩/犬塚 信博/陳 慰/和田 幸一　(Katayama, Takaharu/Ukai, Ryousuke/Goshonoo, Kazuhiko/Itou, Nobuhiro/Inuzuka, Nobuhiro/Chen, Wei/Wada, Kouichi)

　

25. Centralizers and Monoids in Mathematical Clone Theory (New Aspects of Theoretical Computer Science)----------------------------146

　　　　一橋大学/モントリオール大学　　　町田 元/ローゼンバーグ　(Machida, Hajime/Rosenberg, Ivo G.)

　

26. 表編集のアルゴリズム (計算機科学基礎理論の新展開)------------------------------------------------------------------------------152

　　　　関東学院大学工学部/日本大学文理学部/東洋大学工学部/日本大学文理学部　　　本橋 友江/谷 聖一/土田 賢省/夜久 竹夫　(Motohashi, Tomoe/Tani, Sei'ichi/Tsuchida, Kensei/Yaku, Takeo)

　

27. バンド幅問題に対するvolume respecting embedding法の実験的評価 (計算機科学基礎理論の新展開)-------------------------------------158

　　　　群馬大学工学部/群馬大学工学部/群馬大学工学部　　　駒原 雄祐/中野 泰男/山崎 浩一　(Komahara, Yuusuke/Nakano, Yasuo/Yamazaki, Koichi)

　

28. Test Instance Generation for MAX 2SAT with Fixed Optimal Value (New Aspects of Theoretical Computer Science)-------------------164

　　　　北陸先端科学技術大学院大学情報科学研究科　　　元木 光雄　(Motoki, Mitsuo)

　

29. A Simpler Analysis of Goemans and Williamson's LP-relaxation for MAX SAT (New Aspects of Theoretical Computer Science)---------169

　　　　中央大学理工学部　　　浅野 孝夫　(Asano, Takao)

　

30. More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling (New Aspects of Theoretical Computer Science)-----175

　　　　Department of Mathematical Sciences, Tokyo Denki University/Department of Computing Science, University of California, Riverside/Department of Computing Science, University of Alberta/Dipartimento di Informatica e Telecomunicazioni, Universita di Trento/Department of Computing Science, University of California, Riverside/Protein Informatics Group, Life Sciences Division, Oak Ridge National Laboratory/Protein Informatics Group, Life Sciences Division and Computer Sciences and Mathematics Division, Oak Ridge National Laboratory　　　Chen, Zhi-Zhong/Jiang, Tao/Lin, Guohui/Rizzi, Romeo/Wen, Jianjun/Xu, Dong/Xu, Ying

　

31. 平均次数の高いVC-PMの近似アルゴリズム (計算機科学基礎理論の新展開)-------------------------------------------------------------181

　　　　名古屋大学情報文化学部/名古屋大学人間情報学研究科　　　竹内 元気/築地 立家　(Takeuchi, Genki/Tsukiji, Tatsuie)

　

32. タスクスケジューリングに関する新しい近似アルゴリズムについて (計算機科学基礎理論の新展開)--------------------------------------185

　　　　三重大学工学部/三重大学工学部/三重大学工学部/三重大学工学部　　　片柳 賢二/砂坂 明宏/大山口 通夫/太田 義勝　(Katayanagi, Kenji/Sunasaka, Akihiro/Oyamaguchi, Michio/Ohta, Yoshikatsu)

　

33. Shrinking alternating two-pushdown automata (New Aspects of Theoretical Computer Science)--------------------------------------191

　　　　カッセル大学/早稲田大学教育学部　　　オットー F/守屋 悦朗　(Otto, Friedrich/Moriya, Etsuro)

　

34. Information dynamics of cellular automata : CA computation and information theory (New Aspects of Theoretical Computer Science)---197

　　　　京都大学理学部(元)/大阪工業大学情報科部　　　西尾 英之助/斉藤 隆　(Nishio, Hidenosuke/Saito, Takashi)

　

35. Kolmogorov complexity upper bound of probability in computable POVM measurement (New Aspects of Theoretical Computer Science)---203

　　　　科学技術振興事業団創造科学技術推進事業今井量子計算機構プロジェクト　　　只木 孝太郎　(Tadaki, Kohtaro)

　

36. 一般化ブロックパズルのPSPACE完全性の別証明 (計算機科学基礎理論の新展開)--------------------------------------------------------209

　　　　電気通信大学情報工学科/電気通信大学情報工学科　　　北川 智博/岩田 茂樹　(Kitagawa, Tomohiro/Iwata, Shigeki)

　

37. $m×n$分割表の近似数え上げスキームの提案 (計算機科学基礎理論の新展開)----------------------------------------------------------215

　　　　東京大学情報理工学系/東京大学情報理工学系　　　来嶋 秀治/松井 知己　(Kijima, Shuji/Matsui, Tomomi)

　

38. MPR束における「結び既約元」の数理的性質について (計算機科学基礎理論の新展開)---------------------------------------------------221

　　　　東海大学福岡短期大学/東海大学福岡短期大学　　　宮川 幹平/成嶋 弘　(Miyakawa, Kampei/Narushima, Hiroshi)

　

39. 結び目の非自明性判定問題の計算量について (計算機科学基礎理論の新展開)----------------------------------------------------------227

　　　　東海大学理学部/日本大学文理学部/中央大学理工学部　　　原 正雄/谷 聖一/山本 慎　(Hara, Masao/Tani, Sei'ichi/Yamamoto, Makoto)

　

40. 類推機能をもった対話型シークェント計算証明システムの開発 (計算機科学基礎理論の新展開)------------------------------------------233

　　　　九州工業大学情報工学部/九州工業大学情報工学部/九州工業大学情報工学部　　　山田 敬三/平田 耕一/原尾 政輝　(Yamada, Keizo/Hirata, Kouichi/Harao, Masateru)

　

41. 右辺のみに現れる変数をもつ項書換え系のナローイングに基づく実効的書換えとその停止性 (計算機科学基礎理論の新展開)----------------238

　　　　名古屋大学工学研究科/名古屋大学工学研究科/名古屋大学工学研究科　　　西田 直樹/酒井 正彦/坂部 俊樹　(Nishida, Naoki/Sakai, Masahiko/Sakabe, Toshiki)