No.522

計算機科学の基礎理論

Fundamental Theory of Computer Science

1984/01/30～1984/02/01

野口　正一

NOGUCHI,SHOICHI

目　次

1. 二部グラフの拡張性の評価について(計算機科学の基礎理論)----------------------------------------------------------------------------1

　　　　東北大学工学部 / 東北大学工学部　　　神保秀司 / 丸岡章

2. 辺付加によるグラフの拡大構成問題(計算機科学の基礎理論)---------------------------------------------------------------------------16

　　　　広島大学工学部 / 広島大学工学部 / 広島大学大学院工学研究科　　　渡辺敏正 / 中村昭 / 高橋昌也

3. Partitioning a Polygonal Region into Trapezoids----------------------------------------------------------------------------------26

　　　　Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo / Faculty of Engineering, Osaka Electro-Communication University / Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo　　　ASANO, Takao / ASANO, Tetsuo / IMAI, Hiroshi

4. Topics on Triangulation of Polygons----------------------------------------------------------------------------------------------53

　　　　Osaka Electro-Communication University / Faculty of Engineering, University of Tokyo　　　浅野哲夫 / 浅野孝夫　(Asano, Tetsuo / Asano, Takao)

5. On Depth Complete Problems-------------------------------------------------------------------------------------------------------62

　　　　京都大学工学部　　　安浦寛人　(Yasuura, Hiroto)

6. k log n決定性領域を必要とする問題(計算機科学の基礎理論)--------------------------------------------------------------------------77

　　　　東海大学 / 電気通信大学　　　岩田茂樹 / 笠井琢美　(Iwata, Shigeki / Kasai, Takumi)

7. 格子巡回セールスマン問題の近似解法について(計算機科学の基礎理論)-----------------------------------------------------------------90

　　　　電気通信大学 / 電気通信大学　　　三上完治 / 町田元　(Mikami, Kanji / Machida, Hajime)

8. LSI設計の配線におけるグラフの分割(計算機科学の基礎理論)-------------------------------------------------------------------------105

　　　　広島大学工学部 / 広島大学工学部 / 広島大学工学部　　　藤井隆志 / 若林真一 / 菊野亨　(FUJII, Takashi / WAKABAYASHI, Shin'ichi / KIKUNO, Tohru)

9. SET-UP AND ROUTING ALGORITHMS FOR CELLULAR INTERCONNECTION NETWORK--------------------------------------------------------------120

　　　　Research Institute of Electrical Communication, Tohoku University / Research Institute of Electrical Communication, Tohoku University　　　HARAO, Masateru / LOMTONG, Paisan

10. A HASHING METHOD OF FINDING THE MAXIMA OF A SET OF VECTORS---------------------------------------------------------------------131

　　　　Department of Computer Science, Gunma University / Department of Computer Science, Gunma University　　　町井優美 / 五十嵐善英　(Machii, Masami / Igarashi, Yoshihide)

11. Identities for the divisor generating functions and insertion into a heap------------------------------------------------------146

　　　　山梨大学工学部　　　内村桂輔　(Uchimura, Keisuke)

12. An analogue of McMillan's theorem for the counting entropies-------------------------------------------------------------------155

　　　　東北大学工学部　　　大黒茂　(Ohkuro, Shigeru)

13. 正規表現のフォーム記述言語への応用(計算機科学の基礎理論)-----------------------------------------------------------------------172

　　　　広島大学工学部 / 広島大学工学部 / 広島大学工学部　　　杉原一夫 / 宮尾淳一 / 高山雅行[他]　(SUGIHARA, Kazuo / MIYAO, Jun'ichi / TAKAYAMA, Masayuki)

14. Finite Biautomata on Two-way Infinite Words : Preliminary Report---------------------------------------------------------------185

　　　　九州大学教養部　　　林健志　(Hayashi, Takeshi)

15. Two-dimensional Alternating Simple Multihead Finite Automata : Hierarchical Properties-----------------------------------------199

　　　　山口大学工学部 / 山口大学工学部 / 山口大学工学部　　　松野浩嗣 / 谷口弘 / 井上克司[他]　(MATSUNO, Hiroshi / TANIGUCHI, Hiroshi / INOUE, Katsushi)

16. I/O Time Complexity and Synchronization in Iterative(or Systolic) Arrays-------------------------------------------------------212

　　　　Dept. of Applied Electronic Engineering, Faculty of Engineering, Osaka Electro-Communication Univ.　　　梅尾博司　(Umeo, Hiroshi)

17. Structural and Behavioral Equivalence Relations in Automata Networks-----------------------------------------------------------225

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

18. 線形セル構造オートマトンのイデアル論的アプローチII(計算機科学の基礎理論)-------------------------------------------------------240

　　　　東洋大学工学部情報工学科　　　佐藤忠一

19. 指数・対数関数用ハードウェアアルゴリズムについて(計算機科学の基礎理論)---------------------------------------------------------251

　　　　京都大学工学部 / 京都大学工学部　　　高木直史 / 矢島脩三　(TAKAGI, Naofumi / YAJIMA, Shuzo)

20. 入力制約を用いた論理回路の形式的検証について(計算機科学の基礎理論)-------------------------------------------------------------266

　　　　京都大学工学部 / 京都大学工学部 / 京都大学工学部　　　木村晋二 / 安浦寛人 / 矢島脩三　(Kimura, Shinji / Yasuura, Hiroto / Yajima, Shuzo)

21. 異なる並行制御方式を持つデータベースシステムの統合(計算機科学の基礎理論)-------------------------------------------------------280

　　　　京都大学工学部 / 京都大学工学部　　　近藤誠一 / 上林弥彦　(Kondoh, Sei-ichi / Kambayashi, Yahiko)

22. 結合節付加による不等号質問の処理(計算機科学の基礎理論)-------------------------------------------------------------------------295

　　　　京都大学工学部 / 京都大学工学部　　　吉川正俊 / 上林弥彦　(Yoshikawa, Masatoshi / Kambayashi, Yahiko)

23. A relation between the size of term and the number of reduction steps in lambda calculus computations--------------------------308

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