No.1148

2000/01/31〜2000/02/02

渡辺　　治

Osamu Watanabe

目　次

1. 自己双対クロンのrigidity問題 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)--------------------------------------------1

　　　　筑波技術短期大学/モントリオール大学　　　宮川 正弘/ローゼンバーグ Ivo. G.　(Miyakawa,Masahiro/Rosenberg,Ivo. G.)

　

2. 多様な属性関係を表現できるフレーム構造論理の拡張体系 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)--------------------5

　　　　山形大学工学部電子情報工学科/山形大学工学部電子情報工学科/山形大学工学部電子情報工学科　　　小松 香爾/西原 典孝/堀越 浩司　(Komatsu,Koji/Nishihara,Noritaka/Horikoshi,Koji)

　

3. 知的自動証明機の提案と実装 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---------------------------------------------11

　　　　広島市立大学情報科学部/広島市立大学情報科学部　　　新井 紀子/舛川 竜治　(Arai,Noriko H./Masukawa,Ryuji)

　

4. レベル付き依存グラフを用いた効率のよいソフトウェア・パイプライン化法について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---17

　　　　三重大学工学部/三重大学工学部/三重大学工学部　　　武市 雅俊/大山口 通夫/太田 義勝　(Takeichi,Masatoshi/Oyamaguchi,Michio/Ohta,Yoshikatsu)

　

5. An Attribute Precedence Graph Grammar and Tabular Forms (Foundations of Computer Science)----------------------------------------23

　　　　日本大学総合基礎科学科/日本大学総合基礎科学科　　　有田 友和/冨山 聖宣　(Arita,Tomokazu/Tomiyama,Kiyonobu)

　

6. Semi-Right-Terminating 一意解析可能文法による決定性文脈自由言語族の特徴付け (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---29

　　　　広島大学工学部/広島大学工学部　　　森田 憲一/李 佳　(Morita,Kenichi/Lee,Jia)

　

7. 3次元一意解析可能アレイ文法による図形の生成と認識について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)--------------35

　　　　広島大学工学部/広島大学工学部/広島大学工学部/広島大学工学部　　　松田 行雄/森田 憲一/岩本 宙造/今井 克暢　(Matsuda,Yukio/Morita,Kenichi/Iwamoto,Chuzo/Imai,Katsunobu)

　

8. 単一パラメータ・マクロ木変換機とSpine Grammarの関係 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)--------------------41

　　　　電気通信大学情報工学専攻　　　藤芳 明生　(Fujiyoshi,Akio)

　

9. An extention of Grover's quantum search algorithm (Foundations of Computer Science)----------------------------------------------47

　　　　日本電信電話(株)情報流通プラットフォーム研究所　　　田中 圭介　(Tanaka,Keisuke)

　

10. 非線形量子計算の模倣における領域量について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)----------------------------52

　　　　電気通信大学電気通信学科研究科/電気通信大学電気通信学科研究科　　　金田 直樹/西野 哲朗　(Kanada,Naoki/Nishino,Tetsuro)

　

11. Phase-ShiftとControlled-Notで構成される量子回路について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---------------58

　　　　北陸先端科学技術大学院大学情報科学研究科/北陸先端科学技術大学院大学情報科学研究科　　　安倍 秀明/宋 少秋　(Abe,Hideaki/Sung,Shao Chin)

　

12. 正則パターン上の決定木の学習アルゴリズム (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)------------------------------64

　　　　大阪府立大学理学系研究科/大阪府立大学総合科学部/大阪府立大学総合科学部　　　寺田 幹治/向内 康人/佐藤 優子　(Terada,Mikiharu/Mukouchi,Yasuhito/Sato,Masako)

　

13. 質問と正の反例による正則言語の多項式時間学習 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)--------------------------70

　　　　電気通信大学電気通信学研究科電子情報学専攻/電気通信大学電気通信学研究科電子情報学専攻　　　但馬 康宏/富田 悦次　(Tajima,Yasuhiro/Tomita,Etsuji)

　

14. $O(\log n)$長の単調単項式の負例学習について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---------------------------76

　　　　名古屋大学人間情報学研究科/名古屋大学人間情報学研究科　　　築地 立家/徳谷 崇　(Tsukiji,Tatsuie/Tokutani,Takashi)

　

15. 競争型ネットワークサービスモデルの価格戦略に関するゲーム論的考察 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)------82

　　　　九州大学工学部電気情報工学科/九州大学システム情報科学研究科情報工学専攻　　　古賀 健太郎/桜井 幸一　(Koga,Kentaro/Sakurai,Koichi)

　

16. 反復型アルゴリズムによるフィボナッチ列の生成について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)------------------88

　　　　茨城大学工学部情報工学科/茨城大学工学部情報工学科　　　三河 賢治/仙波 一郎　(Mikawa,Kenji/Semba,Ichiro)

　

17. Recognizing Ordered Tree-Shellable Boolean Functions Based on OBDDs (Foundations of Computer Science)---------------------------94

　　　　電気通信大学　　　武永 康彦　(Takenaga,Yasuhiko)

　

18. 系統樹最節約復元束の完備分配性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)-------------------------------100

　　　　電気通信大学大学院/東海大学高輪短期大学部　　　宮川 幹平/成嶋 弘　(Miyakawa,Kampei/Narushima,Hiroshi)

　

19. 系統樹最節約復元の部分木に関する最小性について : Some properties of the distortion index on all MPRs (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---106

　　　　電気通信大学大学院/東海大学高輪短期大学部　　　宮川 幹平/成嶋 弘　(Miyakawa,Kampei/Narushima,Hiroshi)

　

20. A New Definition of Semantic Security for Public-Key Encryption Schemes (Foundations of Computer Science)----------------------112

　　　　群馬大学工学部/群馬大学工学部/群馬大学工学部　　　酒井 秀晃/中村 雅子/五十嵐 善英　(Sakai,Hideaki/Nakamura,Noriko/Igarashi,Yoshihide)

　

21. 弱いランダム仮定の元での公開鍵暗号の強秘匿性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)-----------------118

　　　　通信・放送機構横浜リサーチセンター/東京工業大学数理計算科学専攻　　　小柴 健史/渡辺 治　(Koshiba,Takeshi/Watanabe,Osamu)

　

22. 安定結婚問題の近似可能性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)-------------------------------------124

　　　　京都大学情報学研究科/京都大学情報学研究科/京都大学情報学研究科/京都大学情報学研究科　　　盛田 保文/宮崎 修一/岩間 一雄/ハルダースソン マグナス　(Morita,Yasufumi/Miyazaki,Shuichi/Iwama,Kazuo/Halldorsson,Magnus)

　

23. 3次元直方体のintersection graphに対する独立点集合問題の近似困難について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---130

　　　　群馬大学工学部情報工学科/群馬大学工学部情報工学科　　　長島 弘幸/山崎 浩一　(Nagashima,Hiroyuki/Yamazaki,Koichi)

　

24. Complexity of Grobner Bases for Toric Ideals of Acyclic Tournament Graphs (Foundations of Computer Science)--------------------134

　　　　東京大学理学部/東京大学理学部　　　石関 隆幸/今井 浩　(Ishizeki,Takayuki/Imai,Hiroshi)

　

25. 平均時計算量における2-tt還元とmany-one還元の違いについて (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)-------------140

　　　　名古屋大学人間情報学研究科/名古屋大学人間情報学研究科　　　築地 立家/相田 慎　(Tsukiji,Tatsuie/Aida,Shin)

　

26. 一般化詰め将棋のPSPACE困難性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---------------------------------146

　　　　名古屋大学人間情報学研究科/名古屋大学人間情報学研究科　　　横田 雅也/築地 立家　(Yokota,Masaya/Tsukiji,Tatsuie)

　

27. 不完全情報環境下における時系列データと仮説推論による行動決定 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---------152

　　　　名古屋工業大学電気情報工学科/北陸先端科学技術大学院大学知識科学研究科/名古屋工業大学電気情報工学科/名古屋工業大学電気情報工学科/名古屋工業大学電気情報工学科　　　大塚 忠広/篠田 孝祐/伊藤 暢浩/陳 慰/和田 幸一　(Otsuka,Tadahiro/Shinoda,Kosuke/Ito,Nobuhiro/Chen,Wei/Wada,Koichi)

　

28. 位置情報をもつグラフデータに対する知識表現言語 : Layout Formal Graph System (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---158

　　　　広島市立大学情報科学研究科/広島市立大学情報科学研究科/広島市立大学情報科学研究科/広島市立大学情報科学研究科　　　糸川 裕子/内田 智之/宮原 哲浩/中村 泰明　(Itokawa,Yuko/Uchida,Tomoyuki/Miyahara,Tetsuhiro/Nakamura,Yasuaki)

　

29. Polynomial Time Matching Algorithms for Tree Structured Patterns (Foundations of Computer Science)-----------------------------164

　　　　九州大学システム情報科学科/広島市立大学情報科学研究科/広島市立大学情報科学研究科　　　正代 隆義/宮原 哲浩/内田 智之　(Shoudai,Takayoshi/Miyahara,Tetsuhiro/Uchida,Tomoyuki)

　

30. 確率一般化LR構文解析の先読み方式変更による拡張 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)-----------------------170

　　　　岡山理科大学総合情報学部/豊橋技術科学大学知識情報工学系　　　椎名 広光/増山 繁　(Siina,Hiromitsu/Masuyama,Shigeru)

　

31. Deduction and Abduction with Ordered Binary Decision Diagrams (Foundations of Computer Science)--------------------------------175

　　　　奈良先端科学技術大学院大学/京都大学情報学研究科　　　堀山 貴史/茨木 俊秀　(Horiyama,Takashi/Ibaraki,Toshihide)

　

32. 正則グラフ上の単純投票に対する平均合意時間 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---------------------------181

　　　　福岡教育大学教育学部　　　中田 寿夫　(Nakata,Toshio)

　

33. ラインダイグラフの底グラフにおける完全独立全域木 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---------------------187

　　　　電気通信大学情報工学科　　　蓮沼 徹　(Hasunuma,Toru)

　

34. 2次元スタッキングルーラーオートマトン (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)--------------------------------193

　　　　山口大学理工学研究科/山口大学工学部/山口大学工学部/山口大学工学部　　　坂井 浩二/伊藤 暁/井上 克司/王 躍　(Sakai,Koji/Ito,Akira/Inoue,Katsushi/Wang,Tsu)

　

35. 決定性プッシュダウンオートマトンを模倣する拡張単純回帰ネットワークの構成法 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---200

　　　　電気通信大学電気通信学研究科/電気通信大学電気通信学研究科　　　守谷 純之介/西野 哲朗　(Moriya,Junnosuke/Nishino,Tetsuro)

　

36. 離散対数問題へのPVM(Parallel Virtual Machine)の適応 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)------------------206

　　　　群馬大学工学部情報工学科/群馬大学工学部情報工学科/群馬大学工学部情報工学科　　　森田 雄介/茂木 和弘/五十嵐 善英　(Morita,Yusuke/Motegi,Kazuhiro/Igarashi,Yoshihide)

　

37. 木ネットワークでヒープ順序を実現する自己安定プロトコル (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---------------212

　　　　奈良先端科学技術大学院大学情報科学研究科/奈良先端科学技術大学院大学情報科学研究科/奈良先端科学技術大学院大学情報科学研究科/奈良先端科学技術大学院大学情報科学研究科/奈良先端科学技術大学院大学情報科学研究科　　　長谷川 学/浮穴 学慈/片山 喜章/増沢 利光/藤原 秀雄　(Hasegawa,Manabu/Ukena,Satoshige/Katayama,Yoshiaki/Masuzawa,Toshimitsu/Fujiwara,Hideo)

　

38. 伸長係数2のコンパクトラウティングアルゴリズム (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)------------------------219

　　　　京都大学情報学研究科/京都大学情報学研究科　　　河内 亮周/岩間 一雄　(Kawachi,Akinori/Iwama,Kazuo)

　

39. リーダ選出可能な確率的分散アルゴリズムの初期条件 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)---------------------225

　　　　東京工業大学情報理工学研究科　　　坂本 直志　(Sakamoto,Naoshi)