No.1148
計算機科学の基礎理論:21世紀の計算パラダイムを目指して
Foundations of Computer Science
研究集会報告集
 
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)