No.1205

2001/01/29〜2001/01/31

加藤　直樹

Naoki Katoh

目　次

1. An Extended Depth-first Search : How to Decrease Backtracking (New Developments of Theory of Computation and Algorithms)----------1

　　　　神戸商科大学　　　木庭 淳　(Kiniwa,Jun)

　

2. A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraphs (New Developments of Theory of Computation and Algorithms)---7

　　　　京都大学情報学研究科数理工学専攻/豊橋技術科学大学情報工学系/京都大学情報学研究科数理工学専攻　　　趙 亮/永持 仁/茨木 俊秀　(Zhao,Liang/Nagamochi,Hiroshi/Ibaraki,Toshihide)

　

3. Necessary and Sufficient Numbers of Cards for Sharing Secret Keys on Hierarchical Groups (New Developments of Theory of Computation and Algorithms)---13

　　　　東北大学情報科学研究科/東北大学情報科学研究科　　　水木 敬明/西関 隆夫　(Mizuki,Takaaki/Nishizeki,Takao)

　

4. On the Power of Cooperating Systems of One-way Hybrid Finite Automata (New Developments of Theory of Computation and Algorithms)---19

　　　　山口大学工学部/山口大学工学部/山口大学工学部/山口東京理科大学　　　王 躍/井上 克司/伊藤 暁/岡崎 世雄　(Wang,Yue/Inoue,Katsushi/Ito,Akira/Okazaki,Tokio)

　

5. 定数幅量子ブランチングプログラムの計算能力 (計算理論とアルゴリズムの新展開)------------------------------------------------------25

　　　　奈良先端科学技術大学院大学情報科学研究科/大阪大学基礎工学研究科/大阪大学基礎工学研究科　　　中西 正樹/浜口 清治/柏原 敏伸　(Nakanishi,Masaki/Hamaguchi,Kiyoharu/Kashiwabara,Toshinobu)

　

6. Number conservingなセル空間での自己増殖 (計算理論とアルゴリズムの新展開)---------------------------------------------------------31

　　　　広島大学工学研究科/広島大学工学研究科/広島大学工学研究科/広島大学工学研究科　　　藤田 研二/森田 憲一/岩本 宙造/今井 克暢　(Fujita,Kenji/Morita,Kenichi/Iwamoto,Chuzo/Imai,Katsunobu)

　

7. A parallel algorithm for finding all hinge vertices of a trapezoid graph (New Developments of Theory of Computation and Algorithms)---37

　　　　釧路工業高等専門学校情報工学科/豊橋技術科学大学知識情報工学系　　　本間 宏利/増山 繁　(Honma,Hirotoshi/Masuyama,Shigeru)

　

8. Application of Attribute edNCE Graph Grammars to Syntactic Editing of Tabular Forms (New Developments of Theory of Computation and Algorithms)---43

　　　　日本大学文理学部応用数学科/日本大学文理学部応用数学科/東洋大学工学部情報工学科/日本大学文理学部応用数学科　　　冨山 聖宣/有田 友和/土田 賢省/夜久 竹夫　(Tomiyama,Kiyonobu/Arita,Tomokazu/Tsuchida,Kensei/Yaku,Takeo)

　

9. ジャンケンの計算量 (計算理論とアルゴリズムの新展開)------------------------------------------------------------------------------47

　　　　山口大学工学部知能情報システム工学科/山口大学工学部知能情報システム工学科/山口大学工学部知能情報システム工学科/山口東京理科大学基礎工学部電子基礎工学科　　　伊藤 暁/井上 克司/王 躍/岡崎 世雄　(Ito,Akira/Inoue,Katsushi/Wang,Yue/Okazaki,Tokio)

　

10. 量子公開鍵暗号とその改良 (計算理論とアルゴリズムの新展開)-----------------------------------------------------------------------53

　　　　NTT情報流通プラットフォーム研究所/NTT情報流通プラットフォーム研究所　　　田中 圭介/岡本 龍明　(Tanaka,Keisuke/Okamoto,Tatsuaki)

　

11. Lockout Avoidance Algorithms without Using Time-Stamps for the $k$-Exclusion Problem (New Developments of Theory of Computation and Algorithms)---59

　　　　群馬大学工学部/群馬大学工学部/群馬大学工学部　　　大森 透子/小保方 久美子/五十嵐 善英　(Omori,Michiko/Obokata,Kumiko/Igarashi,Yoshihide)

　

12. Pre-checkingを用いた効率的2階述語マッチングアルゴリズム (計算理論とアルゴリズムの新展開)----------------------------------------65

　　　　九州工業大学情報工学部/九州工業大学情報工学部/九州工業大学情報工学部/九州工業大学情報工学部　　　久保 憲吾/山田 敬三/平田 耕一/原尾 政輝　(Kubo,Kengo/Yamada,Keizo/Hirata,Kouichi/Harao,Masateru)

　

13. Discovery of Maximally Frequent Tag Tree Patterns in Semistructured Data (New Developments of Theory of Computation and Algorithms)---71

　　　　広島市立大学情報科学部/九州大学システム情報科学研究院/広島市立大学情報科学部　　　宮原 哲浩/正代 隆義/内田 智之　(Miyahara,Tetsuhiro/Shoudai,Takayoshi/Uchida,Tomoyuki)

　

14. Simulation of One-Dimensional Cellular Automata by Uniquely Parallel Parsable Grammars (New Developments of Theory of Computation and Algorithms)---77

　　　　広島大学工学部/広島大学工学部/広島大学工学部　　　李 佳/今井 克暢/森田 憲一　(Lee,Jia/Imai,Katsunobu/Morita,Kenichi)

　

15. Tree-Shellable論理関数の判定の複雑さ (計算理論とアルゴリズムの新展開)-----------------------------------------------------------83

　　　　電気通信大学電気通信学研究科情報工学専攻/電気通信大学電気通信学研究科情報工学専攻　　　門野 伸史/武永 康彦　(Kadono,Shinji/Takenaga,Yasuhiko)

　

16. A polynomial time approximation scheme for the minimum maximal matching problem in planar graphs (New Developments of Theory of Computation and Algorithms)---89

　　　　豊橋技術科学大学情報工学系/京都大学情報学研究科数理工学専攻/京都大学情報学研究科数理工学専攻　　　永持 仁/西田 幸弘/茨木 俊秀　(Nagamochi,Hiroshi/Nishida,Yukihiro/Ibaraki,Toshihide)

　

17. An Improved Randomized Algorithm for 3-SAT (New Developments of Theory of Computation and Algorithms)---------------------------95

　　　　//東京工業大学情報理工学研究科数理計算科学専攻　　　//渡辺 治　(Schuler,Rainer/Schoning,Uwe/Watanabe,Oasamu)

　

18. 一意解析可能アレイ文法による単連結図形及び単純閉曲線の生成 (計算理論とアルゴリズムの新展開)------------------------------------101

　　　　広島大学工学部/広島大学工学部/広島大学工学部　　　斉 金山//森田 憲一　(Qi,Jin-Shan/Shauri,Ruhizan Liza Ahmad/Morita,Kenichi)

　

19. A Universal Self-Stabilizing Mutual Exclusion Algorithm (New Developments of Theory of Computation and Algorithms)-------------107

　　　　広島大学工学研究科/九州大学システム情報科学研究院　　　角川 裕次/山下 雅史　(Kakugawa,Hirotsugu/Yamashita,Masafumi)

　

20. SATのいくつかの部分問題の複雑さについて (計算理論とアルゴリズムの新展開)-------------------------------------------------------113

　　　　京都大学情報学研究科通信情報システム専攻/京都大学情報学研究科通信情報システム専攻　　　松浦 昭洋/岩間 一雄　(Matsuura,Akihiro/Iwama,Kazuo)

　

21. 枝の重みが確率的なグラフにおける最長路の長さの分布 (計算理論とアルゴリズムの新展開)--------------------------------------------119

　　　　九州大学システム情報科学研究科/福岡教育大学教育学部/九州大学システム情報科学研究院　　　今林 裕/中田 寿夫/山下 雅史　(Imahayashi,Hiroshi/Nakata,Toshio/Yamashita,Masafumi)

　

22. 系統樹最節約復元の部分木に関する最小性についてII (計算理論とアルゴリズムの新展開)----------------------------------------------125

　　　　電気通信大学情報工学専攻/東海大学短期大学部情報・ネットワーク学科　　　宮川 幹平/成嶋 弘　(Miyakawa, Kampei/Narushima, Hiroshi)

　

23. MAX DICUT問題の近似解法 (計算理論とアルゴリズムの新展開)-----------------------------------------------------------------------131

　　　　東京大学工学系研究科計数工学専攻/東京大学工学系研究科計数工学専攻　　　松浦 史郎/松井 知己　(Matsuura,Shirou/Matsui,Tomomi)

　

24. グラフ演算による最適な故障診断可能システムの構成 (計算理論とアルゴリズムの新展開)----------------------------------------------136

　　　　群馬大学工学部情報工学科/群馬大学工学部情報工学科　　　荒木 徹/柴田 幸夫　(Araki,Toru/Shibata,Yukio)

　

25. A Catalog for Prediction-Preserving Reducibility with Membership Queries on Formal Languages (New Developments of Theory of Computation and Algorithms)---142

　　　　九州工業大学情報工学部/九州大学システム情報科学研究院/九州大学システム情報科学研究院　　　平田 耕一/坂本 比呂志/有村 博紀　(Hirata,Kouichi/Sakamoto,Hiroshi/Arimura,Hiroki)

　

26. Topological Optimization Models for Communication Network with Multiple Reliablity Goals (New Developments of Theory of Computation and Algorithms)---148

　　　　/城西大学理学部数学科　　　/岩村 覚三　(Liu,Baoding/Iwamura,Kakuzo)

　

27. Unrestricted $LR(k)$ Grammars and its Parser, where $k=0,1$ (New Developments of Theory of Computation and Algorithms)---------154

　　　　岡山理科大学総合情報学部/豊橋技術科学大学知識情報工学系　　　椎名 広光/増山 繁　(Shiina,Hiromitsu/Masuyama,Shigeru)

　

28. Deriving Parameter Conditions for Periodic Timed Automata Satisifying Real-Time Temporal Logic Formulas (New Developments of Theory of Computation and Algorithms)---160

　　　　大阪大学基礎工学研究科情報数理系　　　中田 明夫　(Nakata,Akio)

　

29. 有界経路重なり項書換え系の停止性問題について (計算理論とアルゴリズムの新展開)--------------------------------------------------166

　　　　奈良先端科学技術大学院大学情報科学研究科/奈良先端科学技術大学院大学情報科学研究科/奈良先端科学技術大学院大学情報科学研究科/奈良先端科学技術大学院大学情報科学研究科　　　阿部 武徳/高井 利憲/楫 勇一/関 浩之　(Abe,Takenori/Takai,Toshinori/Kaji,Yuichi/Seki,Hiroyuki)

　

30. Galois Connection between Clones and Full Monoids (New Developments of Theory of Computation and Algorithms)-------------------172

　　　　一橋大学/筑波技術短期大学/モントリオール大学　　　町田 元/宮川 正弘/ローゼンバーグ　(Machida,Hajime/Miyakawa,Masahiro/Rosenberg,Ivo G.)

　

31. circulant制約を持った隣接色制約付き彩色問題の応用と解析 (計算理論とアルゴリズムの新展開)---------------------------------------178

　　　　豊橋技術科学大学情報工学系/豊橋技術科学大学情報工学系/豊橋技術科学大学情報工学系/豊橋技術科学大学情報工学系/豊橋技術科学大学情報工学系　　　上嶋 章宏/真田 亜希子/伊藤 大雄/上原 秀幸/横山 光雄　(Uejima,Akihiro/Sanada,Akiko/Ito,Hiro/Uehara,Hideyuki/Yokoyama,Mitsuo)

　

32. The Competitiveness of Diversified Investment on Portfolio Selection Problem (New Developments of Theory of Computation and Algorithms)---183

　　　　会津大学/会津大学　　　岩田 諭/大川 知　(Iwata,Satoshi/Okawa,Satoshi)

　

33. 量子モデルと確率モデルの確率計算の違いによって生じる計算能力の差について (計算理論とアルゴリズムの新展開)----------------------188

　　　　京都大学情報学研究科/京都大学情報学研究科　　　天野 正己/岩間 一雄　(Amano,Masami/Iwama,Kazuo)

　

34. Turing機械と等価な単純回帰ネットワークの構成法 (計算理論とアルゴリズムの新展開)------------------------------------------------194

　　　　電気通信大学電気通信学研究科/電気通信大学電気通信学研究科　　　守谷 純之介/西野 哲朗　(Moriya,Junnosuke/Nishino,Tetsuro)

　

35. Isomorphic factorization of the Kronecker product of generalized de Bruijn digraphs (New Developments of Theory of Computation and Algorithms)---200

　　　　群馬大学工学部情報工学科/群馬大学工学部情報工学科　　　河合 博之/柴田 幸夫　(Kawai,Hiroyuki/Shibata,Yukio)

　

36. 消去可能および消去不能変数を含む正則パターンの効率的な帰納学習 (計算理論とアルゴリズムの新展開)--------------------------------206

　　　　大阪府立大学理学系研究科/大阪府立大学総合科学部　　　植村 仁/佐藤 優子　(Uemura,Jin/Sato,Masako)