No.871
計算量理論
　
1994/02/01〜1994/02/03
丸岡 章
Akira Maruoka
　
目　次
　
1. A Hierarchy Result of Cooperating Systems of Two-Way Counter Machines-------------------------------------------------------------1
　　　　Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University / Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University / Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University　　　王 躍 / 井上 克司 / 高浪 五男　(Wang, Yue / Inoue, Katsushi / Takanami, Itsuo)
　
2. Some Hierarchy Results of Alternating Automata with Counters and Stack-Counters---------------------------------------------------8
　　　　徳山高等専門学校 / 山口大学 / 山口大学　　　義永 常宏 / 井上 克司 / 高浪 五男　(Yoshinaga, Tsunehiro / Inoue, Katsushi / Takanami, Itsuo)
　
3. Optimal Simulation of Two-Dimensional Alternating Finite Automata by Three-Way Nondeterministic Turing Machines------------------15
　　　　山口大学工学部 / 山口大学工学部 / 山口大学工学部　　　伊藤 暁 / 井上 克司 / 高浪 五男　(ITO, Akira / INOUE, Katsushi / TAKANAMI, Itsuo)
　
4. リバーサル限定交代チューリング機械の交代数について(計算量理論)-------------------------------------------------------------------24
　　　　信州大学工学部　　　山本 博章　(Yamamoto, Hiroaki)
　
5. A Complexity Theoretic Approach to Breaking Cryptosystems Based on Discrete Logarithms-------------------------------------------29
　　　　九州大学 / 東北大学　　　櫻井 幸一 / 静谷 啓樹　(SAKURAI, Kouichi / SHIZUYA, Hiroki)
　
6. 量子Turing機械によるNP完全問題の多項式時間解法について(計算量理論)---------------------------------------------------------------30
　　　　北陸先端科学技術大学院大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科　　　三原 孝志 / 西野 哲朗　(Mihara, Takashi / Nishino, Tetsuro)
　
7. 木状Hajos Calculusの非多項式時間限定性(計算量理論)-------------------------------------------------------------------------------37
　　　　九州大学工学部　　　岩間 一雄　(Iwama, Kazuo)
　
8. Uniquely Parsable Grammars-------------------------------------------------------------------------------------------------------45
　　　　広島大学工学部 / 国立民族学博物館 / 山形大学工学部　　　森田 憲一 / 山本 泰則 / 西原 典孝[他]　(MORITA, Kenichi / YAMAMOTO, Yasunori / NISHIHARA, Noritaka)
　
9. LOGICAL FORMULAS FOR PETRI NET $\omega$-LANGUAGES--------------------------------------------------------------------------------52
　　　　一橋大学　　　山崎 秀記　(YAMASAKI, Hideki)
　
10. A Graph Medial Axis Transform---------------------------------------------------------------------------------------------------59
　　　　Department of Applied Mathematics, Hiroshima University / Computer Center, Yarmouk University / Department of Computer Science, Meiji University　　　會澤 邦夫 / ナセル ターヘル / 中村 昭　(Aizawa, Kunio / Naser, Taher / Nakamura, Akira)
　
11. 1次元可逆セル・オートマトンにおける一斉射撃問題について(計算量理論)-------------------------------------------------------------66
　　　　広島大学工学部 / 広島大学工学部　　　今井 克暢 / 森田 憲一　(IMAI, Katsunobu / MORITA, Kenich)
　
12. 正論理関数の最大潜伏度の同定(計算量理論)----------------------------------------------------------------------------------------73
　　　　Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University / Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University　　　牧野 和久 / 茨木 俊秀　(MAKINO, Kazuhisa / IBARAKI, Toshihide)
　
13. On the Computational Power of Binary Decision Diagram with Redundant Variables--------------------------------------------------80
　　　　Department of Information Systems, Interdisciplinary Graduate School of Engineering Sciences, Kyushu University / Department of Information Systems, Interdisciplinary Graduate School of Engineering Sciences, Kyushu University　　　山田 哲也 / 安浦 寛人　(YAMADA, Tetsuya / YASUURA, Hiroto)
　
14. On the Size of Ordered Binary Decision Diagrams Representing Threshold Functions------------------------------------------------87
　　　　Department of Information Science, Facutly of Engineering, Kyoto Unviersity / Department of Information Science, Facutly of Engineering, Kyoto Unviersity / Department of Information Science, Facutly of Engineering, Kyoto Unviersity　　　保坂 和寿 / 武永 康彦 / 矢島 脩三　(HOSAKA, Kazuhisa / TAKENAGA, Yasuhiko / YAJIMA, Shuzo)
　
15. 否定数限定反転回路の複雑さの下界について(計算量理論)----------------------------------------------------------------------------94
　　　　北陸先端科学技術大学院大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科　　　田中 圭介 / 西野 哲朗　(Tanaka, Keisuke / Nishino, Tetsuro)
　
16. ネットワークにおける辺の重要度の評価について(計算量理論)-----------------------------------------------------------------------100
　　　　豊橋技術科学大学知識情報工学系 / 豊橋技術科学大学知識情報工学系　　　程 鵬 / 増山 繁　(CHENG, Peng / MASUYAMA, Shigeru)
　
17. Efficient algorithms for Disjoint Paths in Hypercubes and Star Networks--------------------------------------------------------105
　　　　Department of Computer Software, The University of Aizu / Department of Computer Software, The University of Aizu / Department of Computer Software, The University of Aizu　　　Gu Qian Ping / 大川 知 / Peng Shietung　(Gu, Qian Ping / Okawa, Satoshi / Peng, Shietung)
　
18. SATへの変換を利用したグラフ問題の難しさの評価方法について(計算量理論)----------------------------------------------------------112
　　　　九州大学工学部 / 九州大学工学部　　　宮崎 修一 / 岩間 一雄　(Miyazaki, Shuichi / Iwama, Kazuo)
　
19. $\alpha$連結成分問題の計算複雑さの上昇について(計算量理論)---------------------------------------------------------------------117
　　　　九州大学工学部 / 九州大学工学部　　　岩本 宙造 / 岩間 一雄　(Iwamoto, Chuzo / Iwama, Kazuo)
　
20. Randomized Algorithms for Variance-Based $k$-Clustering------------------------------------------------------------------------124
　　　　Department of Information Science, University of Tokyo / Department of Management Science, Kobe University of Commerce / Department of Information Science, University of Tokyo　　　稲葉 真理 / 加藤 直樹 / 今井 浩　(Inaba, Mary / Katoh, Naoki / Imai, Hiroshi)
　
21. Simulating Fair Dice with a Small Set of Rationally Biased Coins---------------------------------------------------------------130
　　　　東京工業大学総合理工学研究科 / 東京工業大学総合理工学研究科　　　伊東 利哉 / 望月 貴裕　(Itoh, Toshiya / Mochiduki, Takahiro)
　
22. On checkers, Self-Testers, and Self-Debuggers----------------------------------------------------------------------------------138
　　　　東京工業大学総合理工学研究科 / 東京工業大学総合理工学研究科　　　森 啓悦 / 伊東 利哉　(Mori, Hiroyoshi / Itoh, Toshiya)
　
23. LR構文解析の並列アルゴリズムについて(計算量理論)-------------------------------------------------------------------------------145
　　　　豊橋技術科学大学知識情報工学系 / 豊橋技術科学大学知識情報工学系　　　椎名 広光 / 増山 繁　(Shiina, Hiromitsu / Masuyama, Shigeru)
　
24. Finding Maximal Cycle-Free Sets in Parallel------------------------------------------------------------------------------------154
　　　　Dept. of Information Engineering, Mie University / Dept. of Computer Science, State Univ. of New York　　　陳 致中 / He Xin　(Chen, Zhi-Zhong / He, Xin)
　
25. Efficient Parallel Shortest Path Algorithms for Banded Matrices----------------------------------------------------------------161
　　　　Department of Computer Science, University of Kentucky / Department of Computer Science, Gunma University　　　韓 以捷 / 五十嵐 善英　(Han, Yijie / Igarashi, Yoshihide)
　
26. 分散システムにおける資源割り当てアルゴリズム(計算量理論)-----------------------------------------------------------------------168
　　　　広島大学工学部第二類 / 広島大学工学部第二類　　　角川 裕次 / 山下 雅史　(Kakugawa, Hirotsugu / Yamashita, Masafumi)
　
27. 拡張された分散$k$-相互排除(計算量理論)-----------------------------------------------------------------------------------------175
　　　　広島大学工学部 / 広島大学工学部 / 広島大学工学部　　　宮本 英典 / 角川 裕次 / 山下 雅史　(Miyamoto, Hidenori / Kakugawa, Hirotsugu / Yamashita, Masafumi)
　
28. Tight Bound on the Competitive Ratio for the Page Replication Problem----------------------------------------------------------182
　　　　マックスプランクインスティテュート / 東京大学理学部情報科学科　　　アルベルス スザンヌ / 古賀 久志　(Albers, Susanne / Koga, Hisashi)
　
29. 遺伝アルゴリズムにおける交叉法に対する一考察(計算量理論)-----------------------------------------------------------------------190
　　　　京都大学工学部 / 京都大学工学部　　　柳浦 睦憲 / 茨木 俊秀　(YAGIURA, Mutsunori / IBARAKI, Toshihide)
　
30. ハイパーグラフ分割問題に対する分散遺伝的アルゴリズム(計算量理論)---------------------------------------------------------------197
　　　　広島大学工学部 / 広島大学工学部　　　上土井 陽子 / 若林 真一　(Kamidoi, Yoko / Wakabayashi, Shin'ichi)
　
31. LEARNING MONOTONE LOG-TERM DNF FORMULAS----------------------------------------------------------------------------------------204
　　　　Graduate School of Information Sciences, Tohoku University / Graduate School of Information Sciences, Tohoku University　　　酒井 義文 / 丸岡 章　(Sakai, Yoshifumi / Maruoka, Akira)
　
32. 非線形TRSのE重なり性判定問題について(計算量理論)-------------------------------------------------------------------------------212
　　　　三重大学工学部 / 三重大学工学部 / 三重大学工学部　　　松浦 邦博 / 大山口 通夫 / 太田 義勝　(Matsuura, Kunihiro / Oyamaguchi, Michio / Ohta, Yoshikatsu)
　
33. 時間制約付LOTOSの等価性の証明(計算量理論)--------------------------------------------------------------------------------------219
　　　　大阪大学基礎工学部情報工学科 / 大阪大学基礎工学部情報工学科 / 大阪大学基礎工学部情報工学科　　　中田 明夫 / 東野 輝夫 / 谷口 健一　(NAKATA, Akio / HIGASHINO, Teruo / TANIGUCHI, Kenichi)
　
34. 『論語』における価値と感情の論理(計算量理論)-----------------------------------------------------------------------------------226
　　　　日本大学理工学部数学科　　　高橋 英之　(Takahashi, Hideyuki)
　
35. 進化系統樹の最節約復元(MPR)問題について(計算量理論)----------------------------------------------------------------------------233
　　　　東海大学理学部情報数理学科　　　成嶋 弘　(Narushima, Hiroshi)
　
36. 逆探索法を用いた正則単体分割の列挙(計算量理論)---------------------------------------------------------------------------------241
　　　　東京大学大学院理学系研究科情報科学専攻　　　正田 備也　(MASADA, Tomonari)
　
37. チェス盤上の配置問題について(計算量理論)---------------------------------------------------------------------------------------248
　　　　茨城大学教養学部　　　仙波 一郎　(Semba, Ichiro)