No.943
計算量理論の諸相 ― その基礎的研究
　
1995/06/12〜1995/06/16
守屋 悦朗
Etsuro Moriya
　
目　次
　
1. Complexity Classes Characterized by Semi-Random Sources---------------------------------------------------------------------------1
　　　　Center for Information Science, Tokyo Woman's Christian University　　　上原 隆平　(Uehara, Ryuhei)
　
2. Practical PTAS for Maximum Induced-Subgraph Problems on $K_{3,3}$-free of $K_5$-free Graphs--------------------------------------15
　　　　Department of Mathematical Sciences, Tokyo Denki University　　　陳 致中　(Chen, Zhi-Zhong)
　
3. 否定数限定反転回路の複雑さ(計算量理論の諸相 : その基礎的研究)--------------------------------------------------------------------29
　　　　電気通信大学電子情報学科　　　西野 哲朗　(Nishino, Tetsuro)
　
4. 計算の複雑さの平均的な解析について(計算量理論の諸相 : その基礎的研究)------------------------------------------------------------35
　　　　東京工業大学情報理工学研究科計算工学専攻　　　渡辺 治　(WATANABE, Osamu)
　
5. Variable Ordering and the Size of Ordered Binary Decision Diagrams Representing Threshold Functions------------------------------45
　　　　Faculty of Engineering, Kyoto University / Faculty of Engineering, Kyoto University / Faculty of Engineering, Kyoto University　　　武永 康彦 / 金田 高幸 / 矢島 脩三　(TAKENAGA, Yasuhiko / KANEDA, Takayuki / YAJIMA, Shuzo)
　
6. 二分決定グラフに基づく計算複雑さに関する未解決問題について(計算量理論の諸相 : その基礎的研究)------------------------------------56
　　　　奈良先端科学技術大学　　　高木 一義　(Takagi, Kazuyoshi)
　
7. マージングネットワークにおけるある下界について(計算量理論の諸相 : その基礎的研究)------------------------------------------------63
　　　　電気通信大学情報工学科 / 電気通信大学情報工学科 / 電気通信大学情報工学科　　　水野 響 / 増田 一寿 / 岩田 茂樹　(Mizuno, Hibiki / Masuda, Kazuhisa / Iwata, Shigeki)
　
8. A supergraph technique for search problems---------------------------------------------------------------------------------------73
　　　　University of Electro-Communications　　　山崎 浩一　(Yamazaki, Koichi)
　
9. Efficient Drawing Algorithms on the Minimum Area for Tree-Structured Diagrams----------------------------------------------------79
　　　　Department of Information and Computer Sciences, Toyo University / Department of Applied Mathematics, Nihon University　　　土田 賢省 / 夜久 竹夫　(Tsuchida, Kensei / Yaku, Takeo)
　
10. restricted RNLC グラフ言語の学習(計算量理論の諸相 : その基礎的研究)-------------------------------------------------------------88
　　　　東海大学理学部数学科 / 電気通信大学情報工学科　　　谷 聖一 / 山崎 浩一　(Tani, Sei'ichi / Yamazaki, Koichi)
　
11. 強連結オートマトンとその商オートマトンの自己同型群(計算量理論の諸相 : その基礎的研究)-------------------------------------------97
　　　　都留文科大学　　　植村 憲治　(Uemura, Kenji)
　
12. Variants of alternating grammars-----------------------------------------------------------------------------------------------106
　　　　早稲田大学教育学部　　　守屋 悦朗　(Moriya, Etsuro)