No.876
計算量をめぐる基礎的研究
Fundamental Studies on Computational Complexity
 
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
    一橋大学情報処理センター   坂本 直志