No.950

1996/01/31〜1996/02/02

稲垣 康善

Yasuyoshi Inagaki

目　次

1. 単調関数とその主項集合を表すOBDDサイズの関係について(計算モデルと計算の複雑さに関する研究)----------------------------------------1

　　　　東京大学大学院理学系研究科情報科学専攻　　　早瀬 千善　(HAYASE, Kazuyoshi)

　

2. NP完全なブール関数に対する多項式時間スライス関数について(計算モデルと計算の複雑さに関する研究)------------------------------------8

　　　　東海大学理学部数学科 / 電気通信大学情報工学科 / 電気通信大学情報通信工学専攻　　　谷 聖一 / 山崎 浩一 / 西野 哲朗　(Tani, Sei'ichi / Yamazaki, Koichi / Nishino, Tetsuro)

　

3. 単調論理関数と擬似補関数に対する近似モデル(計算モデルと計算の複雑さに関する研究)-------------------------------------------------15

　　　　東北大学大学院情報科学研究科 / 東北大学大学院情報科学研究科　　　天野 一幸 / 丸岡 章　(AMANO, Kazuyuki / MARUOKA, Akira)

　

4. A Note on the Length of M-Programs over Nonsolvable Groups-----------------------------------------------------------------------22

　　　　Department of Mathematics, College of Humanities and Science, NIHON University　　　TODA, Seinosuke

　

5. PRAMおよび対数時間一様な論理回路族に基づく計算量の階層(計算モデルと計算の複雑さに関する研究)-------------------------------------26

　　　　九州芸術工科大学 / 九州大学工学部　　　岩本 宙造 / 岩間 一雄　(Iwamoto, Chuzo / Iwama, Kazuo)

　

6. On the Computational Power of Quantum Turing Machine-----------------------------------------------------------------------------33

　　　　School of Information Science, Japan Advanced Institute of Science and Technology　　　三原 考志　(Mihara, Takashi)

　

7. ある制限されたチャイニーズ・ポストマン問題の計算量(計算モデルと計算の複雑さに関する研究)-----------------------------------------39

　　　　東京電機大学 / 東京電機大学　　　遠山 宏明 / 足立 暁生　(Tohyama, Hiroaki / Adachi, Akeo)

　

8. 進化生物学における離散最適化問題の解法について : 祖先形質復元問題に対する線形時間アルゴリズム(計算モデルと計算の複雑さに関する研究)---46

　　　　東海大学理学部情報数理学科　　　成嶋 弘　(Narushima, Hiroshi)

　

9. On designing optimal on-line algorithms for task systems against random players--------------------------------------------------56

　　　　九州大学工学部情報工学科 / 九州大学工学部情報工学科　　　山家 明男 / 櫻井 幸一　(YANBE, Akio / SAKURAI, Kouichi)

　

10. An Unbiased Global Coin Flipping Protocol on Synchronous Distributed Systems----------------------------------------------------63

　　　　Division of Applied Systems Science, Faculty of Engineering, Kyoto University / Data Processing Center, Kyoto University / Data Processing Center, Kyoto University　　　依田 邦和 / 岡部 寿男 / 金澤 正憲　(Yoda, Kunikazu / Okabe, Yasuo / Kanazawa, Masanori)

　

11. The algorithmic aspect of "probabilistic method independent number theorem"-----------------------------------------------------71

　　　　電気通信大学情報工学科　　　山崎 浩一

　

12. 積グラフの独立な全域木(計算モデルと計算の複雑さに関する研究)--------------------------------------------------------------------73

　　　　群馬大学工学部情報工学科 / 群馬大学工学部情報工学科 / 群馬大学工学部情報工学科　　　小保方 幸次 / 岩崎 至宏 / 鮑 豊[他]　(Obokata, Koji / Iwasaki, Yukihiro / Bao, Feng)

　

13. Sequential and Parallel Approximation of Maximum Induced-Subgraph Problems on Sparse Graphs-------------------------------------80

　　　　Dept. of Math. Sci., Tokyo Denki Univ.　　　陳 致中　(Chen, Zhi-Zhong)

　

14. Approximation algorithms for scheduling problems with generalized due dates-----------------------------------------------------87

　　　　School of Information Science, Japan Advanced Institute of Science and Technology-Hokuriku / School of Information Science, Japan Advanced Institute of Science and Technology-Hokuriku　　　Tanaka, Keisuke / Vlach, Milan

　

15. The Distributed Anonymous Resource Conflict Resolution Problem------------------------------------------------------------------94

　　　　広島大学 / 広島大学 / 広島大学　　　朱 潔平 / 角川 裕次 / 藤田 聡[他]

　

16. 複数プロセス故障を許した耐故障分散相互排除アルゴリズム(計算モデルと計算の複雑さに関する研究)-----------------------------------101

　　　　広島大学工学部 / 広島大学工学部 / 広島大学工学部　　　武川 茂樹 / 若林 真一 / 小出 哲士

　

17. Maintaining a Dynamic Set of Processors in a Distributed System----------------------------------------------------------------106

　　　　Department of Electrical Engineering, Faculty of Engineering, Hiroshima University / Department of Electrical Engineering, Faculty of Engineering, Hiroshima University　　　Fujita, Satoshi / Yamashita, Masafumi

　

18. Fast $RNC$ and $NC$ Algorithms for Maximal Path Sets and Applications to Superstrings with Flipping----------------------------113

　　　　東京女子大学 / 東京電機大学 /　　　上原 隆平 / 陳 致中 /　(Uehara, Ryuhei / Chen, Zhi-Zhong / He, Xin)

　

19. An Optimal Algorithm for the Angle-Restricted All Nearest Neighbor Problem on the Reconfigurable Mesh--------------------------120

　　　　名古屋工業大学電気情報工学科 /　　　中野 浩嗣 /　(Nakano, Koji / Olariu, Stephan)

　

20. Enimeration of Regular Triangulations------------------------------------------------------------------------------------------126

　　　　中央大学理工学部情報工学科 / 東京大学理学部情報科学科　　　今井 桂子 / 今井 浩　(Imai, Keiko / Imai, Hiroshi)

　

21. Tutte多項式とJones多項式の計算(計算モデルと計算の複雑さに関する研究)-----------------------------------------------------------133

　　　　東京大学情報科学研究科 / 東京大学情報科学研究科　　　関根 京子 / 今井 浩　(Sekine, Kyoko / Imai, Hiroshi)

　

22. Type Consistency Problems for Queries in Object-Oriented Databases-------------------------------------------------------------140

　　　　奈良先端科学技術大学院大学情報科学研究科 / 奈良先端科学技術大学院大学情報科学研究科 / 奈良先端科学技術大学院大学情報科学研究科　　　石原 靖哲 / 関 浩之 / 伊藤 実　(ISHIHARA, Yasunori / SEKI, Hiroyuki / ITO, Minoru)

　

23. 2層プラナー(計画器)の提案:自然言語理解のために(計算モデルと計算の複雑さに関する研究)-------------------------------------------146

　　　　日本大学理工学部数学科　　　高橋 英之　(Takahashi, Hideyuki)

　

24. NVNF-sequentiality of Left-linear Term Rewriting Systems-----------------------------------------------------------------------153

　　　　School of Information Science, JAIST / School of Information Science, JAIST / School of Information Science, JAIST　　　長谷 崇 / 酒井 正彦 / 外山 芳人　(Nagaya, Takashi / Sakai, Masahiko / Toyama, Yoshihito)

　

25. Modular Confluence of Conditional Term Rewriting Systems with Extra Variables in Right-Hand Sides------------------------------160

　　　　Department of Information and Computer Sciences, Faculty of Engineering Science, Osaka University / Department of Information and Computer Sciences, Faculty of Engineering Science, Osaka University / Department of Information and Computer Sciences, Faculty of Engineering Science, Osaka University　　　服部 哲 / 岡野 浩三 / 東野 輝夫[他]　(Hattori, Satoshi / Okano, Kozo / Higashino, Teruo)

　

26. On the Church-Rosser Property of Non-E-overlapping and Weight-Preserving TRS's-------------------------------------------------167

　　　　三重大学工学部,沖テクノシステムラボラトリ / 三重大学工学部 / 三重大学工学部　　　五味 弘 / 大山口 通夫 / 太田 義勝　(Gomi, Hiroshi / Oyamaguchi, Michio / Ohta, Yoshikatsu)

　

27. 推論加群系と自動証明への応用(計算モデルと計算の複雑さに関する研究)-------------------------------------------------------------174

　　　　(株)東芝,研究開発センター,情報・通信システム研究所　　　山崎 勇　(Yamazaki, Isamu)

　

28. Tractability of Cut-free Gentzen Type Propositional Calculus with Permutation Inference----------------------------------------181

　　　　広島市立大学　　　新井 紀子　(Arai, Noriko H.)

　

29. 知識論理・様相論理の標準形展開基底による特性化(計算モデルと計算の複雑さに関する研究)-------------------------------------------189

　　　　椙山女学園大学 / 名古屋工業大学　　　大芝 猛 / 小橋 一秀　(Ohshiba, Takeshi / Kobashi, Kazuhide)

　

30. 等号を含む第一階時相論理のサブクラスとその恒真性判定問題(計算モデルと計算の複雑さに関する研究)---------------------------------193

　　　　京都大学大学院工学研究科情報工学専攻 / 京都大学大学院工学研究科情報工学専攻　　　浜口 清治 / 矢島 脩三　(HAMAGUCHI, Kiyoharu / YAJIMA, Shuzo)

　

31. 時間値による状態爆発を回避した時間的双模倣等価性検証法(計算モデルと計算の複雑さに関する研究)-----------------------------------200

　　　　大阪大学基礎工学部情報工学科 / 大阪大学基礎工学部情報工学科 / 大阪大学基礎工学部情報工学科　　　中田 明夫 / 東野 輝夫 / 谷口 健一　(NAKATA, Akio / HIGASHINO, Teruo / TANIGUCHI, Kenichi)

　

32. A Translation Procedure for Elementary Formal Systems--------------------------------------------------------------------------207

　　　　九州工業大学情報工学部知能情報工学科 / 九州工業大学情報工学部知能情報工学科　　　杉本 典子 / 石坂 裕毅　(Sugimoto, Noriko / Ishizaka, Hiroki)

　

33. 多段階木変換機について(計算モデルと計算の複雑さに関する研究)-------------------------------------------------------------------214

　　　　電気通信大学情報工学科 / 電気通信大学情報工学科 / 電気通信大学情報工学科　　　藤芳 明生 / 黒川 浩一 / 笠井 琢美　(Fujiyoshi, Akio / Kurokawa, Koichi / Kasai, Takumi)

　

34. unrestricted LR 文法及び unrestricted LR 構文解析法の提案(計算モデルと計算の複雑さに関する研究)--------------------------------221

　　　　豊橋技術科学大学 / 豊橋技術科学大学　　　椎名 広光 / 増山 繁　(Shiina, Hiromitsu / Masuyama, Shigeru)

　

35. 2次元可逆セル・オートマトンにおける一斉射撃問題(計算モデルと計算の複雑さに関する研究)------------------------------------------228

　　　　広島大学工学部 / 広島大学工学部 / 広島大学工学部　　　安達 太一 / 古阪 真一 / 今井 克暢[他]　(ADACHI, Taichi / FURUSAKA, Shinichi / IMAI, Katsunobu)

　

36. 有限曖昧経営オートマトンの等価性判定問題の可解性(計算モデルと計算の複雑さに関する研究)-----------------------------------------233

　　　　岡山大学工学部情報工学科 / 岡山大学工学部情報工学科　　　橋口 功三郎 / 石黒 賢一　(Hashiguchi, Kosaburo / Ishiguro, Kenichi)

　

37. 近似解をも考慮に入れた多項式時間変換(計算モデルと計算の複雑さに関する研究)-----------------------------------------------------240

　　　　九州大学工学部 / 九州大学工学部　　　宮崎 修一 / 岩間 一雄　(Miyazaki, Shuichi / Iwama, Kazuo)

　

38. 正則パターン言語和の包含に関する強コンパクト性(計算モデルと計算の複雑さに関する研究)-------------------------------------------246

　　　　九州工業大学情報工学部 / 九州工業大学情報工学部　　　有村 博紀 / 篠原 武

　

39. Learnability of Subsequence Languages------------------------------------------------------------------------------------------250

　　　　Research Institute of Fundamental Information Science, Kyushu University / Research Institute of Fundamental Information Science, Kyushu University　　　松本 哲志 / 篠原 歩　(MATSUMOTO, Satoshi / SHINOHARA, Ayumi)