No.833
計算機構とアルゴリズム
　
1993/02/01〜1993/02/03
茨木 俊秀
Toshihide Ibaraki
　
目　次
　
1. co-NP集合のNP集合による近似について(計算機構とアルゴリズム)-----------------------------------------------------------------------1
　　　　九州大学工学部情報工学科　　　岩間 一雄
　
2. The Complexity of Selecting Maximal Solutions------------------------------------------------------------------------------------11
　　　　Department of Information Engineering, Mie University / Department of Computer Science, University of Electro-Communications　　　Chen, Zhi-Zhong / Toda, Seinosuke
　
3. 指定された分布パラメータを満足するSATの例題生成について(計算機構とアルゴリズム)--------------------------------------------------22
　　　　九州大学工学部情報工学科 / 九州大学工学部情報工学科　　　宮野 英次 / 岩間 一雄　(Miyano, Eiji / Iwama, Kazuo)
　
4. 関数のオラクルを用いた計算(計算機構とアルゴリズム)-------------------------------------------------------------------------------31
　　　　南メイン大学 / ボストン大学 / 電気通信大学　　　Fenner Stephan / Homer Steve / 萩原 光徳[他]　(Fenner, Stephan / Homer, Steve / Ogiwara, Mitsunori)
　
5. $\epsilon$-偏りの確率変数と$\epsilon$-依存の確率変数の間の関係について(計算機構とアルゴリズム)-----------------------------------42
　　　　東北大学工学部情報科学研究科 / 東北大学工学部情報科学研究科　　　神保 秀司 / 丸岡 章　(Jimbo, Shuji / Maruoka, Akira)
　
6. Church-Rosser Property and Unique Normal Form Property of Non-Duplicating Term Rewriting Systems : DRAFT-------------------------53
　　　　NTT / Faculty of Engineering, Mie University　　　外山 芳人 / 大山口 通夫　(Toyama, Yoshihito / Oyamaguchi, Michio)
　
7. On the Confluence of Weakly Normalizing TRSs : Note------------------------------------------------------------------------------65
　　　　NTT Communication Science Laboratories　　　山田 順之介　(Yamada, Junnosuke)
　
8. 部分項の評価順が指定できる項書換え系とその性質について(計算機構とアルゴリズム)---------------------------------------------------69
　　　　大阪大学基礎工学部情報工学科 / 大阪大学基礎工学部情報工学科 / 大阪大学基礎工学部情報工学科　　　服部 哲 / 岡野 浩三 / 東野 輝夫[他]　(Hattori, Satoshi / Okano, Kozo / Higashino, Teruo)
　
9. A Lower Bound of the Expected Maximum Number of Edge-disjoint s-t Paths on Probabilistic Graphs----------------------------------80
　　　　豊橋技術科学大学知識情報工学系 / 豊橋技術科学大学知識情報工学系　　　程 鵬 / 増山 繁　(CHENG, Peng / MASUYAMA, Shigeru)
　
10. グラフ節点のある種の線形配列問題について(計算機構とアルゴリズム)----------------------------------------------------------------91
　　　　豊橋技術科学大学知識情報工学系 / 豊橋技術科学大学知識情報工学系 / NTT基礎研究所　　　山本 和英 / 増山 繁 / 内藤 昭三　(YAMAMOTO, Kazuhide / MASUYAMA, Shigeru / NAITO, Shozo)
　
11. グラフの多重目標点分離問題に対する近似アルゴリズムについて(計算機構とアルゴリズム)----------------------------------------------98
　　　　京都大学数理工学科 / 京都大学数理工学科 / 京都大学数理工学科　　　前田 尚久 / 永持 仁 / 茨木 俊秀　(Maeda, Naohisa / Nagamochi, Hitosi / Ibaragi, Tosihide)
　
12. Generalized Geometric Fitting Problems and Weighted Dynamic Voronoi Diagrams---------------------------------------------------110
　　　　中央大学理工学部情報工学科 / 東京大学理学部情報科学科　　　今井 桂子 / 今井 浩　(Imai, Keiko / Imai, Hiroshi)
　
13. A Faster Algorithm for the Minimum Capacity Cut Problem of Undirected Networks-------------------------------------------------120
　　　　Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University / Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University / Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University　　　小野 正 / 永持 仁 / 茨木 俊秀　(ONO, Tadashi / NAGAMOCHI, Hiroshi / IBARAKI, Toshihide)
　
14. 中間経由節点をもつKサーバー問題(計算機構とアルゴリズム)------------------------------------------------------------------------131
　　　　京都大学工学部 / 京都大学工学部　　　軽野 義行 / 茨木 俊秀　(KARUNO, Yoshiyuki / IBARAKI, Toshihide)
　
15. Cooperative Control Algorithms for Anonymous Mobile Robots---------------------------------------------------------------------142
　　　　Department of Electrical Engineering and Computer Science, University of Wisconsin / 広島大学工学部　　　鈴木 一郎 / 山下 雅史　(Suzuki, Ichiro / Yamashita, Masafumi)
　
16. 双方向リングネットワーク上での自己安定2:相互排除(計算機構とアルゴリズム)-------------------------------------------------------153
　　　　広島大学大学院工学研究科情報工学専攻 / 広島大学工学部第二類　　　角川 裕次 / 山下 雅史　(Kakugawa, Hirotsugu / Yamashita, Masafumi)
　
17. 『論語』の公理化⇒孔子のAI化へ:その背景(計算機構とアルゴリズム)----------------------------------------------------------------164
　　　　日本大学理工学部数学科　　　高橋 英之　(Takahashi, Hideyuki)
　
18. A note on one-way multicounter machines and cooperating systems of one-way finite automata-------------------------------------175
　　　　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)
　
19. 形式グラフ体系上の反駁木問題の並列化とグラフ同型問題(計算機構とアルゴリズム)---------------------------------------------------186
　　　　九州大学大学院総合理工学研究科情報システム学専攻 / 山口大学工学部 / 九州大学理学部付属基礎情報学研究施設　　　内田 智之 / 正代 隆義 / 宮野 悟　(Uchida, Tomoyuki / Shoudai, Takayoshi / Miyano, Satoru)
　
20. 確率について或一様性を以って相対化したBPPについて(計算機構とアルゴリズム)------------------------------------------------------197
　　　　法政大学工学部　　　田中 尚夫　(Tanaka, Hisao)
　
21. 組合せ問題の論理関数による解法について(計算機構とアルゴリズム)-----------------------------------------------------------------204
　　　　茨城大学教養学部 / 京都大学工学部　　　仙波 一郎 / 矢島 脩三　(Semba, Ichiro / Yajima, Shuzo)
　
22. 正データからのEFSの帰納推論可能性について:有限の弾力性をもつ言語族のClosure Propertiesとその特徴付け(計算機構とアルゴリズム)---214
　　　　大阪府立大学総合科学部 / 大阪府立大学総合科学部　　　森山 隆史 / 佐藤 優子　(Moriyama, Takashi / Sato, Masako)
　
23. 正論理関数の最大潜伏度について(計算機構とアルゴリズム)-------------------------------------------------------------------------225
　　　　京都大学工学部数理工学科 / 京都大学工学部数理工学科　　　牧野 和久 / 茨木 俊秀　(MAKINO, Kazuhisa / IBARAKI, Toshihide)
　
24. 多項式サイズの二分決定グラフの族に対する完全言語(計算機構とアルゴリズム)-------------------------------------------------------236
　　　　京都大学工学部 / 京都大学工学部 / 京都大学工学部　　　澤田 宏 / 武永 康彦 / 矢島 脩三　(SAWADA, Hiroshi / TAKENAGA, Yasuhiko / YAJIMA, Shuzo)
　
25. NP-completeness of Minimum Binary Decision Diagram Identification Problems-----------------------------------------------------242
　　　　Faculty of Engineering, Kyoto University / Faculty of Engineering, Kyoto University　　　武永 康彦 / 矢島 脩三　(TAKENAGA, Yasuhiko / YAJIMA, Shuzo)
　
26. バス結合型並列計算機におけるデータ転送の最適アルゴリズム(計算機構とアルゴリズム)-----------------------------------------------250
　　　　京都大学工学部 / 京都大学工学部　　　岡部 寿男 / 津田 孝夫　(OKABE, Yasuo / TSUDA, Takao)