No.992

1997/02/03～1997/02/05

谷口健一

Kenichi Taniguchi

目　次

1. A Map from the Lower-Half of the n-Cube onto the (n-1)-Cube which Preserves Intersecting Antichains-------------------------------1

　　　　Tsukuba College of Technology / Otsuma Women's University / International Christian University / Universite de Montreal　　　宮川正弘 / 野崎昭弘 / ポゴシャン G. / ローゼンバーグ I.G.　(Miyakawa, Masahiro / Nozaki, Akihiro / Pogosyan, Grant / Rosenberg, Ivo G.)

2. 系統樹最節約復元問題の大域的最適解について(計算理論とその応用)--------------------------------------------------------------------5

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

3. 最大共通誘導部分グラフ問題のMAX SNP-hardness について(計算理論とその応用)--------------------------------------------------------12

　　　　九州大学大学院システム情報科学研究科情報理学専攻 / 九州大学大学院システム情報科学研究科情報理学専攻　　　杉野孔一 / 正代隆義

4. A Divide and Conquer Approach to the Minimum $k$-Way Cut Problem-----------------------------------------------------------------20

　　　　Faculty of Information Science, Hiroshima City University / Faculty of Engineering, Hiroshima University　　　上土井陽子 / 若林真一　(Kamidoi, Yoko / Wakabayashi, Shin'ichi)

5. Learning Conformation Rules------------------------------------------------------------------------------------------------------28

　　　　Human Genome Center, University of Tokyo / Fukuoka Women's Junior College / Graduate School of Genetic Resources Technology, Kushu University / Human Genome Center, University of Tokyo　　　丸山修 / 古市恵美子 / 久原哲 / 宮野悟　(Maruyama, Osamu / Furuichi, Emiko / Kuhara, Satoru / Miyano, Satoru)

6. 決定性有限メモリーオートマトンの学習可能性(計算理論とその応用)-------------------------------------------------------------------36

　　　　九州大学システム情報科学研究科 / 九州大学システム情報科学研究科　　　坂本比呂志 /　(/ Zeugmann, Thomas)

7. ニューロイダルネット上の学習について(計算理論とその応用)-------------------------------------------------------------------------42

　　　　電気通信大学電子情報学科　　　西野哲朗　(Nishino, Tetsuro)

8. Learning One-Variable Pattern Languages Very Efficiently-------------------------------------------------------------------------47

　　　　Institut fur Informatik, Technische Universitat Munchen / Institut fur Informatik, Technische Universitat Munchen / Dept. of Informatics, Kyushu University　　　ERLEBACH, THOMAS / ROSSMANITH, PETER / ZEUGMANN, THOMAS [他]

9. Learning pattern languages using queries-----------------------------------------------------------------------------------------58

　　　　Department of Informatics, Kyushu University / Department of Informatics, Kyushu University　　　松本哲志 / 篠原歩　(MATSUMOTO, Satoshi / SHINOHARA, Ayumi)

10. 項グラフ言語の正データからの多項式時間帰納推論可能性について(計算理論とその応用)------------------------------------------------66

　　　　九州大学大学院システム情報科学研究科情報理学専攻 / 九州大学大学院システム情報科学研究科情報理学専攻 / 九州大学大学院システム情報科学研究科情報理学専攻　　　林夕起子 / 松本哲志 / 正代隆義

11. $\lambda$-幾何における3点の最小スタイナ木について(計算理論とその応用)-----------------------------------------------------------74

　　　　岡山県立大学情報工学部　　　早瀬道芳　(Hayase, Michiyoshi)

12. Independent Spanning Trees of Chordal Rings-------------------------------------------------------------------------------------82

　　　　Department of Computer Science, Gunma University / Department of Computer Science, Gunma University / Department of Computer Science, Gunma University　　　岩崎至宏 / 梶原由香 / 小保方幸次[他]　(Iwasaki, Yukihiro / Kajiwara, Yuka / Obokata, Koji)

13. Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously-------------------------------------------------------------90

　　　　Kyoto University / Kyoto University / Kyoto University　　　ISHII, Toshimasa / NAGAMOCHI, Hiroshi / IBARAKI, Toshihide

14. Enumerating Triangulations for Arbitrary Configurations of Points and for Products of Two Simplices-----------------------------98

　　　　Department of Information Science, University of Tokyo / Department of Information Science, University of Tokyo / Department of Information and System Engineering, Chuo University　　　竹内史比古 / 今井浩 / 今井桂子　(Takeuchi, Fumihiko / Imai, Hiroshi / Imai, Keiko)

15. 統計パラメタ空間におけるVoronoi diagramの離散構造(計算理論とその応用)----------------------------------------------------------106

　　　　神戸大学自然科学研究科　　　大西建輔

16. An $0(log n)$ parallel algorithm for constructing a spanning forest on Trapezoid graphs----------------------------------------114

　　　　Department of Information Engineering, Kushiro National College of Technology / Department of Knowledge-Based Information Engineering, Toyohashi University of Technology　　　本間宏利 / 増山繁　(Honma, Hirotoshi / Masuyama, Shigeru)

17. CCSに基づく並列処理言語の実装(計算理論とその応用||)----------------------------------------------------------------------------122

　　　　九州大学システム情報科学研究科 / 九州大学システム情報科学研究科　　　原淳 / 森雅生　(Hara, Atsushi / Mori, Masao)

18. モービルプロセス計算の型システムについて(計算理論とその応用)-------------------------------------------------------------------126

　　　　静岡大学情報学部情報科学科　　　富樫敦　(Tohashi, Atsushi)

19. On Product Formula of Tree Expressions-----------------------------------------------------------------------------------------134

　　　　九州大学大学院システム情報科学研究科情報理学専攻 / 九州大学大学院システム情報科学研究科情報理学専攻　　　井口修一 / 河原康雄

20. チューリング機械の領域計算量の厳密な階層について(計算理論とその応用)-----------------------------------------------------------138

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

21. 指数個の決定性状態を必要とする非決定性有限オートマトンについて(計算理論とその応用)---------------------------------------------146

　　　　九州大学大学院システム情報科学研究科 / 九州大学大学院システム情報科学研究科　　　高木和哉 / 岩間一雄　(Takaki, Kazuya / iwama, Kazuo)

22. 計算万能な2次元8状態3角形状可逆セル・オートマン(計算理論とその応用)------------------------------------------------------------154

　　　　広島大学工学部 / 広島大学工学部　　　今井克暢 / 森田憲一　(IMAI, Katsunobu / MORITA, Kenichi)

23. 推論エンジン, 「論語」論理の場合(計算理論とその応用)---------------------------------------------------------------------------159

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

24. $\lambda_C$計算と$\lambda_P$計算との対応(計算理論とその応用)-------------------------------------------------------------------167

　　　　九州大学 / 京都大学 / 九州大学　　　廣川佐千男 / 亀山幸義 / 馬場謙介　(Hirokawa, Sachio / Kameyama, Yukiyoshi / Baba, Kensuke)

25. Lower bounds of the negation-limited circuit complexity------------------------------------------------------------------------175

　　　　School of Information Science, Japan Advanced Institute of Science and Technology / School of Information Science, Japan Advanced Institute of Science and Technology　　　Sung, Shao-Chin / Tanaka, Keisuke

26. Minimum Self-Dual Decompositions of Positive Dual-Minor Boolean Functions------------------------------------------------------183

　　　　Department of Computer Science, Erasmus University / Department of Applied Mathematics and Physics, Graduate School of Engineering, Kyoto University / Department of Applied Mathematics and Physics, Graduate School of Engineering, Kyoto University　　　Bioch, Jan C. / Ibaraki, Toshihide / Makino, Kazuhisa

27. On the Depth of Randomly Generated Circuits------------------------------------------------------------------------------------191

　　　　Dept. of Computer Science, Tokyo Institute of Technology / Dept. of LSI, Faculty of Informatics, UPC　　　築地立家 /　(Tsukiji, Tatsuie / Xhafa, Fatos)

28. 論理関数の複雑さと近似演算(計算理論とその応用)---------------------------------------------------------------------------------199

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

29. The Computational Complexity of Hereditary Elementary Formal Systems-----------------------------------------------------------207

　　　　Department of Informatics, Kyushu University / Department of Informatics, Kyushu University　　　池田大輔 / 有村博紀　(Ikeda, Daisuke / Arimura, Hiroki)

30. ネットワーク上のバックトラックアルゴリズム(計算理論とその応用)-----------------------------------------------------------------215

　　　　茨城大学工学部　　　仙波一郎　(Semba, Ichiro)

31. 複数の予測戦略を統合する実時間予測アルゴリズム(計算理論とその応用)-------------------------------------------------------------223

　　　　東北大学大学院情報科学研究科 / 東北大学大学院情報科学研究科 / 東北大学大学院情報科学研究科　　　田近一郎 / 瀧本英二 / 丸岡章　(TAJIKA, Ichiro / TAKIMOTO, Eiji / MARUOKA, Akira)

32. オンライン先読みページングゲームにおける最適戦略の設計と解析(計算理論とその応用)-----------------------------------------------229

　　　　九州大学大学院システム情報科学研究科 / 九州大学大学院システム情報科学研究科　　　山家明男 / 櫻井幸一　(Yanbe, Akio / Sakurai, Kouichi)

33. 分散相互排除システムの可用度を改善するコーラム再割当アルゴリズム(計算理論とその応用)-------------------------------------------236

　　　　広島大学総合情報処理センター / 広島大学工学部第二類　　　原田隆 / 山下雅史