No.876

1993/06/14〜1993/06/18

町田 元

Hajime Machida

目　次

1. Complexity of Finding Alphabet Indexing(Fundamental Studies on Computational Complexity)------------------------------------------1

　　　　Department of Control Engineering and Science, Kyushu Institute of Technology / Research Institute of Fundamental Information Science, Kyushu University　　　下薗 真一 / 宮野 悟　(Shimozono, Shinichi / Miyano, Satoru)

　

2. Finding Maximal Cycle-Free Subgraphs in Parallel(Fundamental Studies on Computational Complexity)--------------------------------16

　　　　Department of Information Engineering, Mie University　　　Chen, Zhi-Zhong

　

3. A Generalization of Tree Automata and Traversal of Trees(Fundamental Studies on Computational Complexity)------------------------29

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

　

4. 否定数限定回路の複雑さについて(計算量をめぐる基礎的研究)-------------------------------------------------------------------------37

　　　　北陸先端科学技術大学院大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科　　　西野 哲朗 / 田中 圭介　(Nishino, Tetsuro / Tanaka, Keisuke)

　

5. An Exact Minimization of AND-EXOR Expressions Using Reduced Covering Functions(Fundamental Studies on Computational Complexity)---50

　　　　Department of Computer Science and Electronics, Kyushu Institute of Technology　　　笹尾 勤　(SASAO, Tsutomu)

　

6. Hardness of Learning Binary Decision Diagrams(Fundamental Studies on Computational Complexity)-----------------------------------60

　　　　Faculty of Engineering, Kyoto University / Faculty of Engineering, Kyoto University　　　武永 康彦 / 矢島 脩三　(TAKENAGA, Yasuhiko / YAJIMA, Shuzo)

　

7. 高々$n$個の状態数をもつ有限オートマトンのVapnik-Chervonenkis次元について(計算量をめぐる基礎的研究)-------------------------------69

　　　　早稲田大学理工学部数学科 / 東京女子大学情報処理教室　　　石上 嘉康 / 谷 聖一　(Ishigami, Yoshiyasu / Tani, Sei'ichi)

　

8. 一方向関数の相対的な存在に関する考察(計算量をめぐる基礎的研究)-------------------------------------------------------------------83

　　　　一橋大学情報処理センター　　　坂本 直志