No.556

Mathematical Foundations of Computer Science and Their Applications

1985/01/30～1985/02/01

笠井　琢美

KASAI,TAKUMI

目　次

1. On the Nested Heap Structure in Smoothsort(Mathematical Foundations of Computer Science and Their Applications)-------------------1

　　　　Department of Computer Science, Denkitusin University / Department of Computer Science, Denkitusin University　　　野下浩平 / 仲谷栄伸　(Noshita, Kohei / Nakatani, Yoshinobu)

2. 垂直型3層チャネル配線アルゴリズムについて(計算機科学の基礎理論とその応用)--------------------------------------------------------17

　　　　九州工業大学情報工学科　　　永松正博　(Nagamatsu, Masahiro)

3. EFFICIENT IMPLEMENTATIONS OF PARALLEL SORT ALGORITHMS ON A MESH-CONNECTED PROCESSOR ARRAY(Mathematical Foundations of Computer Science and Their Applications)---37

　　　　Department of Computer Science, Gunma University / Department of Computer Science, Gunma University / Department of Computer Science, Gunma University　　　五十嵐善英 / 佐渡一広 / 安達範明　(Igarashi, Yoshihide / Sado, Kazuhiro / Adachi, Noriaki)

4. A Distributed Algorithm for Deadlock Detection in Replicated Database Systems(Mathematical Foundations of Computer Science and Their Applications)---49

　　　　Faculty of Engineering, Hiroshima University / Faculty of Engineering, Hiroshima University / Faculty of Engineering, Hiroshima University　　　Ogata, Masanobu / Sugihara, Kazuo / Kikuno, Tohru

5. データベースシステムの同時処理制御における直列可能性のいくつかのクラスについて(計算機科学の基礎理論とその応用)-------------------59

　　　　京都大学工学部 / 京都大学工学部 / 京都大学工学部　　　木庭淳 / 室章治郎 / 長谷川利治　(Kiniwa, Jun / Muro, Shojiro / Hasegawa, Toshiharu)

6. 条件式グラフの変形による分散データベースの質問処理(計算機科学の基礎理論とその応用)-----------------------------------------------71

　　　　京都大学工学部 / 九州大学工学部　　　吉川正俊 / 上林弥彦　(YOSHIKAWA, Masatoshi / KAMBAYASHI, Yahiko)

7. ネットワークデータベースにおける選択・射影・結合質問の処理(計算機科学の基礎理論とその応用)---------------------------------------81

　　　　京都大学工学部 / 九州大学工学部　　　古川哲也 / 上林彌彦　(Furukawa, Tetsuya / Kambayashi, Yahiko)

8. Redundant Coding and Local Computability in Parallel Computation(Mathematical Foundations of Computer Science and Their Applications)---93

　　　　京都大学工学部 / 京都大学工学部 / 京都大学工学部　　　安浦寛人 / 高木直史 / 矢島脩三　(Yasuura, Hiroto / Takagi, Naofumi / Yajima, Shuzo)

9. 論理回路機能の時間的関係の記述と検証(計算機科学の基礎理論とその応用)------------------------------------------------------------104

　　　　京都大学工学部 / 京都大学工学部　　　木村晋二 / 矢島脩三　(Kimura, Shinji / Yajima, Shuzo)

10. Some system for map generation(Mathematical Foundations of Computer Science and Their Applications)----------------------------116

　　　　Department of Applied Mathematics, Hiroshima University / Theoretical Biology Group, University of Utrecht　　　中村昭 / 会沢邦夫　(Nakamura, Akira / Aizawa, Kunio)

11. Complexity of Combinator Reduction Machine(Mathematical Foundations of Computer Science and Their Applications)----------------122

　　　　静岡大学工学部情報工学科　　　広川佐千男　(Hirokawa, Sachio)

12. 形付項書き換えシステム(計算機科学の基礎理論とその応用)-------------------------------------------------------------------------147

　　　　日本電信電話公社武蔵野電気通信研究所　　　外山芳人　(TOYAMA, Yoshihito)

13. 項書き換えシステムの簡約化戦略について(計算機科学の基礎理論とその応用)---------------------------------------------------------151

　　　　豊橋技術科学大学 / 豊橋技術科学大学 / 豊橋技術科学大学　　　直井徹 / 山下雅史 / 茨木俊秀[他]　(Naoi, Tohru / Yamashita, Masafumi / Ibaraki, Toshihide)

14. オートマタ・ネットワークの構造の解析(計算機科学の基礎理論とその応用)-----------------------------------------------------------163

　　　　Department of Biophysics, Kyoto Univ. / Department of Biophysics, Kyoto Univ. / Department of Biophysics, Kyoto Univ.　　　西尾英之助 / 斉藤隆 / 森田浩一　(Nishio, H. / Saito, T. / Morita, K.)

15. オートマタネットワーク間の類似性について(計算機科学の基礎理論とその応用)-------------------------------------------------------171

　　　　Department of Biophysics, Faculty of Science, Kyoto University / Department of Biophysics, Faculty of Science, Kyoto University　　　斉藤隆 / 西尾英之助　(SAITO, Takashi / NISHIO, Hidenosuke)

16. プログラミング言語PL/0の代数的仕様記述(計算機科学の基礎理論とその応用)---------------------------------------------------------177

　　　　名古屋大学工学部 / 名古屋大学工学部 / 名古屋大学工学部　　　北英彦 / 坂部俊樹 / 稲垣康善

17. 相互通信逐次型プロセス系の検証(計算機科学の基礎理論とその応用)-----------------------------------------------------------------187

　　　　名古屋大学工学部 / 名古屋大学工学部　　　村上昌己 / 稲垣康善

18. 非決定性同時計算量について(計算機科学の基礎理論とその応用)---------------------------------------------------------------------197

　　　　東京女子大学 / 東海大学 / 電気通信大学　　　守屋悦朗 / 岩田茂樹 / 笠井琢美　(Moriya, Etsuro / Iwata, Shigeki / Kasai, Takumi)

19. Positive relativizations of low level complexity classes(Mathematical Foundations of Computer Science and Their Applications)---209

　　　　国文学研究資料館　　　戸田誠之助　(Toda, Seinosuke)

20. 低いレベルの同時計算量について(計算機科学の基礎理論とその応用)-----------------------------------------------------------------219

　　　　電気通信大学　　　関口正裕　(Sekiguchi, Masahiro)

21. A Remark on Solving the Set-Partitioning Problem by Dual All Integer Algorithm(Mathematical Foundations of Computer Science and Their Applications)---231

　　　　Mathematics, Josai University　　　Iwamura, Kakuzo

22. COMPLEXITY OF PATH COVERING PROBLEMS IN ACYCLIC ALTERNATE GRAPHS(Mathematical Foundations of Computer Science and Their Applications)---240

　　　　Tsuru Univ. / Tokai Univ.　　　植村憲治 / 夜久竹夫　(UEMURA, Kenji / YAKU, Takeo)

23. 解の存在が保障されている組合せ探索問題について(計算機科学の基礎理論とその応用)-------------------------------------------------250

　　　　京都産業大学理学部　　　岩間一雄　(Iwama, Kazuo)

24. グラフパッキング問題の計算複雑度(計算機科学の基礎理論とその応用)---------------------------------------------------------------260

　　　　京都大学工学部 / 西北電訊工程学院 / 豊橋技術科学大学　　　増山繁 / 張澤増 / 茨木俊秀[他]

25. 多値論理関数の本質的極小閉集合(計算機科学の基礎理論とその応用)-----------------------------------------------------------------272

　　　　電気通信大学 / モントリオール大学　　　町田元 / Rosenberg Ivo　(Machida, Hajime / Rosenberg, Ivo)

26. On the Semantics of Infinite Computations in Logic Programs(Mathematical Foundations of Computer Science and Their Applications)---282

　　　　Department of Information Science, TOKYO Institute of Technology　　　榊原康文　(Sakakibara, Yasubumi)

27. 知識の表現のための「述語」を持たない述語(?)論理"Tuple Logic"の提案(計算機科学の基礎理論とその応用)-----------------------------294

　　　　大阪大学基礎工学部　　　森田憲一　(MORITA, Kenichi)

28. 時空間様相論理ETSLの完全・無矛盾な公理系(計算機科学の基礎理論とその応用)-------------------------------------------------------306

　　　　東北大学電気通信研究所 / 山形大学工学部 / 東北大学電気通信研究所　　　岩沼宏治 / 原尾政輝 / 野口正一　(IWANUMA, Koji / HARAO, Masateru / NOGUTI, Syoichi)

29. THE COMPLEXITY OF SUBSTITUTIVE PROGRAMS(Mathematical Foundations of Computer Science and Their Applications)-------------------319

　　　　Dept. Math. Sci., Tokai Univ. / Sci. Inst., IBM Japan / Comput. Sci. Div., Electrotech. Lab.　　　Yaku, Takeo / Adachi, Akeo / Futatsugi, Kokichi