No.906
アルゴリズムと計算量理論
 
1995/01/31〜1995/02/02
笠井 琢美
Takumi Kasai
 
目 次
 
1. Isomorphism of restricted chain-like graphs---------------------------------------------------------------------------------------1
    University of Electro-Communications   Yamazaki, Koichi
 
2. A Simple Near Optimal Parallel Algorithm for Recognizing Outerplanar Graphs-------------------------------------------------------6
    Department of Knowledge-Based Information Engineering, Toyohashi University of Technology / Department of Knowledge-Based Information Engineering, Toyohashi University of Technology   中山 慎一 / 増山 繁 (Nakayama, Shin-ichi / Masuyama, Shigeru)
 
3. ジャンケンのトーナメント表現と意味のある拡張(アルゴリズムと計算量理論)-----------------------------------------------------------14
    NTT通信網研究所 / 京都大学工学部   伊藤 大雄 / 永持 仁 (ITO, Hiro / NAGAMOCHI, Hiroshi)
 
4. 巡回セールスマン問題(Traveling Salesman Problem)の貪欲アルゴリズムについて(アルゴリズムと計算量理論)-----------------------------24
    東京工業大学工学部情報工学科   横山 光一 (YOKOYAMA, Mitsukazu)
 
5. マルチエージェントの知識論理における多様相化した推論の正当性について(アルゴリズムと計算量理論)-----------------------------------32
    九州大学総合理工学研究科情報システム学専攻   森 雅生 (Mori, Masao)
 
6. ファジィ関係代数とその表現定理について(アルゴリズムと計算量理論)-----------------------------------------------------------------39
    九州大学総合理工学研究科情報システム学専攻 / 九州大学理学部附属基礎情報学研究施設   古澤 仁 / 河原 康雄 (FURUSAWA, Hitoshi / KAWAHARA, Yasuo)
 
7. 規則限定Resolutionにより証明可能な命題論理式の複雑さ(アルゴリズムと計算量理論)---------------------------------------------------47
    九州大学工学部情報工学科 / 九州大学工学部情報工学科   宮野 英次 / 岩間 一雄 (MIYANO, Eiji / IWAMA, Kazuo)
 
8. A Note on Alternating Pushdown Automata With Sublogarithmic Space----------------------------------------------------------------55
    Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University / Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University / Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University   Xu, Jianliang / Inoue, Katsushi / Wang, Yue[他]
 
9. Alternation for Two-Way(Inkdot) Multi-Counter Automata with Sublinear Space------------------------------------------------------64
    徳山高等専門学校 / 山口大学工学部   義永 常宏 / 井上 克司 (YOSHINAGA, Tsunehiro / INOUE, Katsushi)
 
10. Two Variations of Inductive Inference of Languages from Positive Data-----------------------------------------------------------73
    Research Institute of Fundamental Information Science, Kyushu University / Research Institute of Fundamental Information Science, Kyushu University   田部 尚志 / (Tabe, Takashi / Zeugmann, Thomas)
 
11. Circuit Complexity of An Explicity Defined First Slice Function-----------------------------------------------------------------81
    Dept. of Computer Science, Tokyo Institute of Technology   Tsukiji, Tatsuie
 
12. 対称関数の否定数限定回路計算量について(アルゴリズムと計算量理論)----------------------------------------------------------------89
    北陸先端科学技術大学院大学情報科学研究科 / 電気通信大学電子情報学科   田中 圭介 / 西野 哲朗 (Tanaka, Keisuke / Nishino, Tetsuro)
 
13. 単調並べ換え関数について(アルゴリズムと計算量理論)------------------------------------------------------------------------------96
    東北大学情報科学研究科 / 東北大学情報科学研究科 / 東北大学情報科学研究科   神保 秀司 / 佐々木 宏平 / 山本 佳典[他] (Jimbo, Shuji / Sasaki, Kohei / Yamamoto, Yoshinori)
 
14. 2次元オルタネイティングo(loglog m)領域計算量クラスの補集合に関する非閉包性(アルゴリズムと計算量理論)---------------------------104
    山口大学工学部 / 山口大学工学部 / 山口大学工学部   伊藤 暁 / 井上 克司 / 王 躍 (ITO, Akira / INOUE, Katsushi / WANG, Yue)
 
15. RIGHT CONGRUENCES FOR $\omega$-REGULAR LANGUAGES-------------------------------------------------------------------------------112
    Department of Mathematics, Hitotsubashi University   山崎 秀記 (YAMASAKI, Hideki)
 
16. 1次元可逆セル・オートマトンにおける一斉射撃問題の高速解(アルゴリズムと計算量理論)----------------------------------------------119
    広島大学工学部 / 広島大学工学部   今井 克暢 / 森田 憲一 (IMAI, Katsunobu / MORITA, Kenich)
 
17. 周期1と2のリミットサイクルをもつセルオートマトンについて(アルゴリズムと計算量理論)---------------------------------------------126
    九州大学大学院総合理工学研究科情報システム学専攻 / 九州大学理学部附属基礎情報学研究施設   井口 修一 / 河原 康雄 (INOKUCHI, Syuichi / KAWAHARA, Yasuo)
 
18. 知識命題の標準形を用いる妥当性検証(アルゴリズムと計算量理論)-------------------------------------------------------------------132
    名古屋工業大学 / 名古屋工業大学   大芝 猛 / 小橋 一秀 (OSHIBA, Takeshi / KOBASHI, Kazuhide)
 
19. 自然推論による微積の初歩の完全な形式化とそのプルーフ・チェッカー(アルゴリズムと計算量理論)-------------------------------------138
    日本大学理工学部数学科 / 日本大学理工学部数学科   高橋 英之 / 山下 正人 (Takahashi, Hideyuki / Yamashita, Masato)
 
20. Extension of Synthesis Algorithm of Recursive Processes to $\mu$-calculus------------------------------------------------------146
    電気通信研究所 / 情報科学研究所 / 東北大学   木村 成伴 / 富樫 敦 / 白鳥 則郎 (Kimura, Shigetomo / Togashi, Atsushi / Shiratori, Norio)
 
21. MSCからのプロセス合成(アルゴリズムと計算量理論)--------------------------------------------------------------------------------154
    東北大学電気通信研究所 / 東北大学電気通信研究所 / 東北大学電気通信研究所   臼井 伸幸 / 木村 成伴 / 富樫 敦[他] (USUI, Nobuyuki / KIMURA, Shigetomo / TOGASHI, Atsushi)
 
22. 生態ピラミッドの概念を取り入れた遺伝的アルゴリズムの提案(アルゴリズムと計算量理論)---------------------------------------------162
    広島市立大学情報科学部 / 広島大学工学部 / 広島大学工学部   上土井 陽子 / 岸本 善久 / 若林 真一 (Kamidoi, Yoko / Kishimoto, Yoshihisa / Wakabayashi, Shin'ichi)
 
23. Demonstrating Programs against Adversaries-------------------------------------------------------------------------------------170
    九州大学工学部情報工学科 / 九州大学工学部情報工学科   櫻井 幸一 / 岩間 一雄 (SAKURAI, Kouichi / IWAMA, Kazuo)
 
24. ブール処理のパズルへの応用(アルゴリズムと計算量理論)---------------------------------------------------------------------------178
    茨城大学教養学部   仙波 一郎 (Semba, Ichiro)
 
25. 3分決定グラフを用いた積項集合表現(アルゴリズムと計算量理論)--------------------------------------------------------------------186
    京都大学大型計算機センター   安岡 孝一 (Yasuoka, Koichi)
 
26. 積和形論理式を表す二分決定グラフの表現能力(アルゴリズムと計算量理論)-----------------------------------------------------------196
    京都大学工学部情報工学教室 / 京都大学工学部情報工学教室 / 京都大学工学部情報工学教室   新田 高庸 / 武永 康彦 / 矢島 脩三 (NITTA, Koyo / TAKENAGA, Yasuhiko / YAJIMA, Shuzo)
 
27. On Breadth First Construction of OBDDs Representing Maximal Independent Sets---------------------------------------------------204
    東京大学理学部情報科学科   早瀬 千善 (HAYASE, Kazuyoshi)
 
28. Negative Results for Learing Minor Closed Graph Classes------------------------------------------------------------------------212
    Dept. of Computer Science, Tokyo Institute of Technology / Dept. of Computer Science, Royal Holloway, University of London   Domingo, Carlos / Shawe-Taylor, John
 
29. 正データからのSimple Regular言語の多項式時間帰納推論(アルゴリズムと計算量理論)-------------------------------------------------220
    大阪府立大学総合科学研究科 / 大阪府立大学総合科学研究科   佐藤 清朗 / 佐藤 優子
 
30. 完全データからのSimple Regular言語族の多項式時間反駁推論について(アルゴリズムと計算量理論)-------------------------------------228
    大阪府立大学総合科学研究科 / 大阪府立大学総合科学研究科   渡辺 紀仁 / 佐藤 優子 (WATANABE, Norihito / SATO, Masako)
 
31. Proper learning algorithm for functions of $k$ terms under smooth distributions------------------------------------------------236
    Graduate School of Information Sciences, Tohoku University / Graduate School of Information Sciences, Tohoku University / Graduate School of Information Sciences, Tohoku University   Sakai, Yoshifumi / Takimoto, Eiji / Maruoka, Akira
 
32. 情報を意図的に改変する可能性のある通信路における安全な通信プロトコルのLFKNプロトコルによる改良について(アルゴリズムと計算量理論)---244
    一橋大学情報処理センター   坂本 直志
 
33. Reliable Broadcasting in Product Networks--------------------------------------------------------------------------------------249
    Department of Computer Science, Gunma University / Department of Computer Science, Gunma University / Department of Computer Science, University of North Texas   豊 鮑 / 五十嵐 善英 / オーリング ザビネ (Feng, Bao / Igarashi, Yoshihide / Ohring, Sabine R.)
 
34. リングの方向付け問題を有限状態数で解く自己安定アルゴリズム(アルゴリズムと計算量理論)-------------------------------------------257
    広島大学大学院工学研究科情報工学専攻 / 広島大学工学部第二類 / 広島大学工学部第二類   梅本 成俊 / 角川 裕次 / 山下 雅史 (Umemoto, Narutoshi / Kakugawa, Hirotsugu / Yamashita, Masafumi)
 
35. 自動翻訳における新しい木構造の導入 : 左右木について(アルゴリズムと計算量理論)--------------------------------------------------264
       黒川 浩一 / 笠井 琢美 (Kurokawa, Kouichi / Kasai, Takumi)