No.1093
計算モデルとアルゴリズム
Models of Computation and Algorithms
研究集会報告集
 　
1999/02/01〜1999/02/03
森田　憲一
Kenichi Morita
　
目　次
　
1. 多値論理代数におけるsemirigidity問題 : 自己双対関数について (計算モデルとアルゴリズム)--------------------------------------------1
　　　　筑波技術短期大学　　　宮川 正弘　(Miyakawa, Masahiro)
　
2. Generation of $k$-permutations in $0$(1) time per permutation by reversing sublists (Models of Computation and Algorithms)--------5
　　　　茨城大学理工学研究科/茨城大学工学部　　　三河 賢治/仙波 一郎　(Mikawa, Kenji/Semba, Ichiro)
　
3. Single Machine Scheduling with Generalized Precedence Relations (Models of Computation and Algorithms)---------------------------11
　　　　北陸先端科学技術大学院大学情報科学研究科/NTT情報通信研究所/北陸先端科学技術大学院大学情報科学研究科　　　宋 少秋/田中 圭介/ブラッハ ミラン　(Shao, Chin Sung/Tanaka, Keisuke/Vlach, Milan)
　
4. 一方向通貨交換問題における予測を用いたアルゴリズム (計算モデルとアルゴリズム)----------------------------------------------------15
　　　　京都大学工学部情報学科/京都大学情報学研究科　　　米澤 弘毅/岩間 一雄　(Yonezawa, Kouki/Iwama, Kazuo)
　
5. Computational Geometry on Statistical Manifolds for Clustering : Extended Abstract (Models of Computation and Algorithms)--------21
　　　　東京大学理学部/東京大学理学部/東京大学理学部　　　稲葉 真理/今井 浩/定兼 邦彦　(Inaba, Mary/Imai, Hiroshi/Sadakane, Kunihiko)
　
6. Tractable and Intractable Problems on Generalized Chordal Graphs (Models of Computation and Algorithms)--------------------------27
　　　　駒沢大学人文科学研究科　　　上原 隆平　(Uehara, Ryuhei)
　
7. Common-face embeddings of planar graphs with applications (Models of Computation and Algorithms)---------------------------------33
　　　　東京電機大学理工学部　　　陳 致中　(Chen, Zhi-Zhong/He, Xin/Kao, Ming-Yang)
　
8. Simple algorithm for recognizing lake-free 4-map graphs (Models of Computation and Algorithms)-----------------------------------39
　　　　東京電機大学理工学部数理学科　　　陳 致中　(Chen, Zhi-Zhong)
　
9. On greedy algorithms for maximum weighted independent set problem (Models of Computation and Algorithms)-------------------------45
　　　　群馬大学工学部/群馬大学工学部/群馬大学工学部　　　酒井 周一/戸ヶ崎 光敬/山崎 浩一　(Sakai, Shuichi/Togasaki, Mitsunori/Yamazaki, Koichi)
　
10. 絡み目のJones多項式の計算 (計算モデルとアルゴリズム)----------------------------------------------------------------------------51
　　　　東海大学理学部情報数理学科/日本大学文理学部応用数学科/中央大学理工学部数学科　　　原 正雄/谷 聖一/山本 慎　(Hara, Masao/Tani, Sei'ichi/Yamamoto, Makoto)
　
11. On Extremal Problems of MPR-posets II (Models of Computation and Algorithms)----------------------------------------------------57
　　　　東海大学理学研究科/東海大学短期大学部　　　宮川 幹平/成嶋 弘　(Miyakawa, Kampei/Narushima, Hiroshi)
　
12. 統計量による$\alpha\beta$法の効率化 (計算モデルとアルゴリズム)------------------------------------------------------------------62
　　　　電気通信大学大学院情報工学専攻/電気通信大学大学院情報工学専攻　　　亀田 純也/笠井 琢美　(Kameda, Jyunnya/Sakai, Takumi)
　
13. A Characterization of Min-Wise Independent Permutations Families (Models of Computation and Algorithms)-------------------------68
　　　　東京工業大学総合理工学部/東京工業大学総合理工学部　　　武井 由智/伊東 利哉　(Takei, Yoshinori/Itoh, Toshiya)
　
14. A Polynomial Time Sampling Algorithm for an Optimal Family of Min-Wise Independent Permutations (Models of Computation and Algorithms)---74
　　　　東京工業大学総合理工学部/東京工業大学総合理工学部　　　篠崎 隆宏/伊東 利哉　(Shinozaki, Takahiro/Itoh, Toshiya)
　
15. 部分語計数問題の接尾辞配列を用いた高速アルゴリズム (計算モデルとアルゴリズム)---------------------------------------------------81
　　　　九州大学システム情報科学研究科情報理学専攻/九州大学システム情報科学研究科情報理学専攻/九州大学システム情報科学研究科情報理学専攻　　　笠井 透/有村 博紀/有川 節夫　(Kasai, Toru/Arimura, Hiroki/Arikawa, Setsuo)
　
16. On Gigantic Pairs of Minimal Clones (Models of Computation and Algorithms)------------------------------------------------------87
　　　　一橋大学数学共同研究所　　　町田 元　(Machida, Hajime/Rosenberg, Ivo G.)
　
17. Ordered Binary Decision Diagrams Representing Knowledge-Bases (Models of Computation and Algorithms)----------------------------93
　　　　京都大学情報学研究科/京都大学情報学研究科　　　堀山 貴史/茨木 俊秀　(Horiyama, Takashi/Ibaraki, Toshihide)
　
18. 可変マージ関数の否定数限定複雑さ (計算モデルとアルゴリズム)---------------------------------------------------------------------99
　　　　仙台電波工業高等専門学校/東北大学情報科学研究科/東北大学情報科学研究科　　　佐藤 貴之/天野 一幸/丸岡 章　(Sato, Takayuki/Amano, Kazuyuki/Maruoka, Akira)
　
19. Extended Reversible言語とその正例からの多項式時間帰納推論 (計算モデルとアルゴリズム)-------------------------------------------105
　　　　大阪府立大学総合科学研究科/大阪府立大学総合科学部　　　植村 仁/佐藤 優子　(Uemura, Jin/Sato, Masako)
　
20. 正例からのパターン上の決定木の帰納推論 (計算モデルとアルゴリズム)--------------------------------------------------------------111
　　　　大阪府立大学理学系研究科/大阪府立大学総合科学部/大阪府立大学総合科学部　　　寺田 幹治/向内 康人/佐藤 優子　(Terada, Mikiharu/Mukouchi, Yasuhito/Sato, Masako)
　
21. Refutable Inference of Formal Graph Systems and NLC Graph Grammars (Models of Computation and Algorithms)----------------------117
　　　　広島市立大学情報科学研究科/広島市立大学情報科学研究科/九州大学システム情報科学研究科/広島市立大学情報科学研究科/広島市立大学情報科学研究科　　　宮原 哲浩/内田 智之/正代 隆義/高橋 健一/上田 祐彰　(Miyahara, Tetsuhiro/Uchida, Tomoyuki/Shoudai, Takayoshi/Takahashi, Kenichi/Ueda, Hiroaki)
　
22. Analyzing the Average-Case Bahavior of Conjunctive Learning Algorithms (Models of Computation and Algorithms)------------------123
　　　　/九州大学システム情報科学研究科　　　Reischuk, Rudiger/Zeugmann, Thomas
　
23. Learning DNF by Approximating Inclusion-Exclusion Formulae (Models of Computation and Algorithms)------------------------------130
　　　　電気通信大学情報通信学部/名古屋大学人間情報学部　　　垂井 淳/築地 立家　(Tarui, Jun/Tsukiji, Tatsuie)
　
24. 順序ソートの自動推論とラベル付けに基づく合流性判定への応用 (計算モデルとアルゴリズム)------------------------------------------136
　　　　名古屋大学工学研究科情報工学専攻/名古屋大学工学研究科情報工学専攻/名古屋大学工学研究科情報工学専攻　　　宮下 大/酒井 正彦/坂部 俊樹　(Miyashita, Dai/Sakai, Masahiko/Sakabe, Toshiki)
　
25. スキーママッチングにおける計算の複雑さ (計算モデルとアルゴリズム)--------------------------------------------------------------142
　　　　九州工業大学情報工学部/九州工業大学情報工学部/九州工業大学情報工学部　　　山田 敬三/平田 耕一/原尾 政輝　(Yamada, Keizo/Hirata, Kouichi/Harao, Masateru)
　
26. 代数的仕様における振舞等価性証明のための線形文脈帰納法について (計算モデルとアルゴリズム)--------------------------------------148
　　　　名古屋大学工学研究科情報工学専攻/名古屋大学工学研究科情報工学専攻　　　二井 靖彦/坂部 俊樹　(Nii, Yasuhiko/Sakabe, Toshiki)
　
27. 無証拠複数者間計算 (計算モデルとアルゴリズム)----------------------------------------------------------------------------------155
　　　　九州大学システム情報科学研究科情報工学専攻　　　櫻井 幸一　(Sakurai, Kouichi)
　
28. 分散RSA暗号における鍵生成と復号アルゴリズム (計算モデルとアルゴリズム)---------------------------------------------------------156
　　　　九州大学システム情報科学研究科/九州大学システム情報科学研究科　　　宮崎 真悟/櫻井 幸一　(Miyazaki, Shingo/Sakurai, Kouichi)
　
29. Unpredictability of Pseudorandom Number Generators on Public Key Cryptosystems with Random Inputs (Models of Computation and Algorithms)---162
　　　　通信・放送機構　　　小柴 健史　(Koshiba, Takeshi)
　
30. 最小normal論理Kより小さい擬論理の標準形展開 (計算モデルとアルゴリズム)---------------------------------------------------------168
　　　　椙山女学園大学　　　大芝 猛　(Oshiba, Takeshi)
　
31. ゼロ知識証明の定式化について (計算モデルとアルゴリズム)------------------------------------------------------------------------173
　　　　一橋大学情報処理センター　　　奈古屋 広昭　(Nagoya, Hiroaki)
　
32. Secret Bit Transmission Using a Random Deal of Cards on Hierarchical Structures (Models of Computation and Algorithms)---------176
　　　　群馬大学工学部/群馬大学工学部　　　吉川 玲奈/五十嵐 善英　(Yoshikawa, Reina/Igarashi, Yoshihide)
　
33. ハイパーキューブ上の安全な情報伝達 (計算モデルとアルゴリズム)------------------------------------------------------------------182
　　　　群馬大学工学部情報工学科/群馬大学工学部情報工学科/群馬大学工学部情報工学科/群馬大学工学部情報工学科　　　中村 雅子/酒井 秀晃/西谷 泰昭/五十嵐 善英　(Nakamura, Noriko/Sakai, Hideaki/Nishitani, Yasuaki/Igarashi, Yoshihide)
　
34. 単純回帰ネットワークの計算能力について (計算モデルとアルゴリズム)--------------------------------------------------------------188
　　　　電気通信大学電気通信学研究科/電気通信大学電気通信学研究科　　　守谷 純之介/西野 哲朗　(Moriya, Junnosuke/Nishino, Tetsuro)
　
35. 線形プッシュダウン・木オートマトン (計算モデルとアルゴリズム)------------------------------------------------------------------194
　　　　電気通信大学情報工学研究科/電気通信大学情報工学研究科　　　藤芳 明生/笠井 琢美　(Fujiyoshi, Akio/Kasai, Takumi)
　
36. 量子有限オートマトンにおける決定不能問題 (計算モデルとアルゴリズム)------------------------------------------------------------200
　　　　京都大学工学部情報学科/京都大学情報学研究科　　　天野 正己/岩間 一雄　(Amano, Masami/Iwama, Kazuo)
　
37. 3次元可逆自己増殖セル・オートマトンについて (計算モデルとアルゴリズム)---------------------------------------------------------206
　　　　NECアイシーマイコンシステム/広島大学工学部/広島大学工学部　　　堀 貴博/今井 克暢/森田 憲一　(Hori, Takahiro/Imai, Katsunobu/Morita, Kenichi)
　
38. Two-Point Splicing Systemの言語生成能力の万能性 (計算モデルとアルゴリズム)-----------------------------------------------------212
　　　　広島大学工学部/広島大学工学部/広島大学工学部/広島大学工学部　　　細川 英/森田 憲一/岩本 宙造/今井 克暢　(Hosokawa, Hiroshi/Morita, Kenichi/Iwamoto, Chuzo/Imai, Katsunobu)
　
39. 一意並列解析可能ユニフィケーション文法 (計算モデルとアルゴリズム)--------------------------------------------------------------218
　　　　広島大学工学部/広島大学工学部/広島大学工学部/広島大学工学部　　　李 佳/森田 憲一/岩本 宙造/今井 克暢　(Lee, Jia/Morita, Kenichi/Iwamoto, Chuzo/Imai, Katsunobu)
　
40. あるクラスの文脈依存グラフ文法とその性質 (計算モデルとアルゴリズム)------------------------------------------------------------224
　　　　東洋大学工学部/東洋大学工学部/東洋大学工学部/日本大学文理学部　　　安達 由洋/小林 卓/土田 賢省/夜久 竹夫　(Adachi, Yoshihiro/Kobayashi, Suguru/Tuchida, Kensei/Yaku, Takeo)
　
41. $LC$文法とその構文解析法の拡張について (計算モデルとアルゴリズム)--------------------------------------------------------------230
　　　　岡山理科大学/豊橋技術科学大学　　　椎名 広光/増山 繁　(Shiina, Hiromitsu/Masuyama, Shigeru)
　
42. グラフ上の局所多数決問題の確率的アプローチ (計算モデルとアルゴリズム)----------------------------------------------------------236
　　　　福岡教育大学教育学部/九州大学工学部/九州大学システム情報学部　　　中田 寿夫/今林 裕/山下 雅史　(Nakata, Toshio/Imahayashi, Hiroshi/Yamashita, Masafumi)
　
43. 移動ロボットによる長尺物運搬問題に対する分散アルゴリズム (計算モデルとアルゴリズム)--------------------------------------------242
　　　　九州大学工学部/九州大学システム情報科学研究科/九州大学システム情報科学研究科/ウィスコンシン大学ミルウォーキー校/理化学研究所　　　李 春艶/朝廣 雄一/山下 雅史/鈴木 一郎/浅間 一　(Li, Chunyan/Asahiro, Yuichi/Yamashita, Masafumi/Suzuki, Ichiro/Asama, Hajime)