No.716

1989/06/05〜1989/06/09

町田　元

MACHIDA,HAJIME

目　次

1. Paddable Sets in Number Theory(Complexity Theory and Related Topics)--------------------------------------------------------------1

　　　　Department of Information Science, Tokyo Institute of Technology　　　萩原 光徳　(Ogiwara, Mitsunori)

　

2. 平均計算時間に基づく計算複雑さの研究について(計算量理論とその周辺)---------------------------------------------------------------10

　　　　東京工業大学工学部　　　渡辺 治　(Watanabe, Osamu)

　

3. 有向グラフに対する極大パスカバー問題の計算量(計算量理論とその周辺)---------------------------------------------------------------19

　　　　東京電機大学理工学部 / 都留文科大学 / 東京電機大学理工学部　　　山神 憲司 / 植村 憲治 / 夜久 竹夫　(Yamagami, Kenji / Uemura, Kenji / Yaku, Takeo)

　

4. 弱単項二階論理式の例示および反例からの学習(計算量理論とその周辺)-----------------------------------------------------------------37

　　　　東京電機大学理工学部情報科学科　　　西野 哲朗　(Nishino, Tetsuro)

　

5. On Learning A Class of Context-free Languages in Polynomial Time(Complexity Theory and Related Topics)---------------------------60

　　　　Department of Computer Science, University of Electro-Communications　　　横森 貴　(YOKOMORI, Takashi)

　

6. 推論の並列化(計算量理論とその周辺)-----------------------------------------------------------------------------------------------71

　　　　九州大学理学部基礎情報学研究施設　　　宮野 悟　(MIYANO, Satoru)

　

7. 単項演算に対する局所計算可能な符号化(計算量理論とその周辺)-----------------------------------------------------------------------81

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

　

8. On the Complexity of Three-Level Logic Circuits(Complexity Theory and Related Topics)-------------------------------------------101

　　　　九州工業大学情報工学部　　　笹尾 勤　(SASAO, Tsutomu)

　

9. A METHOD TO COMPUTE LOWER BOUNDS ON CIRCUIT-SIZE COMPLEXITY(Complexity Theory and Related Topics)-------------------------------117

　　　　Hitotsubashi University　　　町田 元　(MACHIDA, Hajime)

　

10. Some Restrictinons on CFGs With Memory(Complexity Theory and Related Topics)---------------------------------------------------124

　　　　東京女子大学文理学部　　　守屋 悦朗　(Moriya, Etsuro)