No.1489
計算理論とアルゴリズムの新展開
New Trends in Theory of Computation and Algorithm
RIMS 研究集会報告集
 　
2006/01/30〜2006/02/01
山下　雅史
Masafumi Yamashita
　
目　次
　
1. 確率時間オートマトンの確率時間弱模倣検証理論(計算理論とアルゴリズムの新展開)------------------------------------------------------1
　　　　金沢大学工学部情報システム工学科 / 金沢大学工学部情報システム工学科　　　橋爪 裕樹 / 山根 智　(Hashizume, Yuki / Yamane, Satoshi)
　
2. 時間オートマトンによる Value-Density スケジューリングアルゴリズムの性能解析手法(計算理論とアルゴリズムの新展開)-------------------8
　　　　金沢大学自然科学研究科 / 金沢大学自然科学研究科　　　坂倉 賢昭 / 山根 智　(Sakakura, Masaaki / Yamane, Satoshi)
　
3. 近傍系はセルオートマトンの大域行動にどう影響するか?(計算理論とアルゴリズムの新展開)----------------------------------------------15
　　　　京都大学理学部(元)　　　西尾 英之助　(Nishio, Hidenosuke)
　
4. CFG/PDA の alternation 付与方法ほかについて(計算理論とアルゴリズムの新展開)------------------------------------------------------22
　　　　早稲田大学教育総合科学学術院　　　守屋 悦朗　(Moriya, Etsuro)
　
5. AND-EXOR 論理式の暗号プロトコルへの応用(計算理論とアルゴリズムの新展開)----------------------------------------------------------29
　　　　東北大学大学院情報科学研究科 / 東北大学情報シナジーセンター / 東北大学情報シナジーセンター　　　小田切 太朗 / 水木 敬明 / 曽根 秀昭　(Otagiri, Taro / Mizuki, Takaaki / Sone, Hideaki)
　
6. 一般的に匿名化可能な暗号方式(計算理論とアルゴリズムの新展開)---------------------------------------------------------------------36
　　　　東京工業大学数理計算科学専攻 / 東京工業大学数理計算科学専攻　　　林 良太郎 / 田中 圭介　(Hayashi, Ryotaro / Tanaka, Keisuke)
　
7. Multi-Bit Cryptosystems based on Lattice Problems : Extended Abstract(New Trends in Theory of Computation and Algorithm)---------43
　　　　Department of Mathematical and Computing Sciences, Tokyo Institute of Technology / Department of Mathematical and Computing Sciences, Tokyo Institute of Technology / Department of Mathematical and Computing Sciences, Tokyo Institute of Technology　　　草川 恵太 / 河内 亮周 / 田中 圭介　(Xagawa, Keita / Kawachi, Akinori / Tanaka, Keisuke)
　
8. オンラインオークション型資源配分問題(計算理論とアルゴリズムの新展開)-------------------------------------------------------------50
　　　　Graduate School of Information Sciences, Tohoku University / Graduate School of Information Sciences, Tohoku University / Graduate School of Information Sciences, Tohoku University　　　原田 薫明 / 瀧本 英二 / 丸岡 章
　
9. より効率的なフィルタリング型ブースティング技法(計算理論とアルゴリズムの新展開)---------------------------------------------------57
　　　　九州大学システム情報科学研究院情報理学部門　　　畑埜 晃平　(Hatano, Kohei)
　
10. Learning of Elementary Formal Systems with Two Clauses using Queries and Their Languages(New Trends in Theory of Computation and Algorithm)---64
　　　　東海大学大学院理学研究科数理科学専攻 / 東海大学理学部情報数理学科 / 広島市立大学情報科学部知能情報システム工学科　　　加藤 浩央 / 松本 哲志 / 宮原 哲浩　(Kato, Hirotaka / Matsumoto, Satoshi / Miyahara, Tetsuhiro)
　
11. 確率単純文法のサブクラスにおける一般化と強化学習への応用(計算理論とアルゴリズムの新展開)----------------------------------------71
　　　　東京大学工学系研究科電子工学専攻 / 東京大学工学系研究科電子工学専攻　　　柴田 剛志 / 近山 隆
　
12. Syntactic Characterization of Two-Dimensional Grid Graphs by a Context-Sensitive Graph Grammar(New Trends in Theory of Computation and Algorithm)---78
　　　　桜美林大学文学部言語コミュニケーション学科 / 東洋大学工学部情報工学科 / 日本大学文理学部情報システム解析学科　　　有田 友和 / 土田 賢省 / 夜久 竹夫　(ARITA, Tomokazu / TSUCHIDA, Kensei / YAKU, Takeo)
　
13. DNA 分子の濃度と反応速度の関係解析(計算理論とアルゴリズムの新展開)--------------------------------------------------------------85
　　　　九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学研究院 / 九州大学大学院システム情報科学研究院　　　塩崎 真史 / 小野 廣隆 / 定兼 邦彦[他]　(Shiozaki, Masashi / Ono, Hirotaka / Sadakane, Kunihiko)
　
14. マルチキュースイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良(計算理論とアルゴリズムの新展開)--------------------91
　　　　京都大学情報学研究科 / 京都大学学術情報メディアセンター / 京都大学学術情報メディアセンター　　　小林 浩二 / 宮崎 修一 / 岡部 寿男　(Kobayashi, Koji / Miyazaki, Shuichi / Okabe, Yasuo)
　
15. Robustness of Greedy Type Minimum Evolution Algorithms(New Trends in Theory of Computation and Algorithm)-----------------------98
　　　　東京工業大学情報理工学研究科数理計算科学専攻　　　繁住 健哉　(Shigezumi, Takeya)
　
16. ビット列で表現された完全二分木の判定アルゴリズム(計算理論とアルゴリズムの新展開)-----------------------------------------------102
　　　　新潟大学大学院自然科学研究科 / 新潟大学総合情報処理センター / 近畿大学工学部　　　漆山 龍哉 / 三河 賢治 / 長谷川 誠　(URUSHIYAMA, Tatsuya / MIKAWA, Kenji / HASEGAWA, Makoto)
　
17. A Message Passing Algorithm for MAX2SAT(New Trends in Theory of Computation and Algorithm)-------------------------------------106
　　　　東京工業大学,情報理工学研究科,数理計算科学専攻 / 東京工業大学,情報理工学研究科,数理計算科学専攻　　　渡辺 治 / 山本 真基　(Watanabe, Osamu / Yamamoto, Masaki)
　
18. Complexity-Theoretical Quantum List Decoding and Applications to Quantum Hardcore Functions(New Trends in Theory of Computation and Algorithm)---114
　　　　Department of Mathematical and Computing Sciences, Tokyo Institute of Technology / ERATO-SORST Quantum Computation and Information Project, Japan Science and Technology Agency　　　河内 亮周 / 山上 智幸　(Kawachi, Akinori / Yamakami, Tomoyuki)
　
19. Geometric Characterization of Quantum Oracle Identification(New Trends in Theory of Computation and Algorithm)-----------------121
　　　　Department of Mathematical and Computing Sciences, Tokyo Institute of Technology / Graduate School of Information Science, Nara Institute of Science and Technology　　　河内 亮周 / 山下 茂　(Kawachi, Akinori / Yamashita, Shigeru)
　
20. 量子ネットワーク上での効率的な情報の伝送(計算理論とアルゴリズムの新展開)-------------------------------------------------------128
　　　　ERATO-SORST量子情報システムアーキテクチャ / 京都大学情報学研究科 / 京都大学情報学研究科　　　林 正人 / 岩間 一雄 / 西村 治道[他]　(HAYASHI, MASAHITO / IWAMA, KAZUO / NISHIMURA, HARUMICHI)
　
21. Upper bounds for quantum biased oracles with explicit bias rate(New Trends in Theory of Computation and Algorithm)-------------135
　　　　奈良先端科学技術大学院大学情報科学研究科 / 奈良先端科学技術大学院大学情報科学研究科 / 奈良先端科学技術大学院大学情報科学研究科　　　鈴木 智哉 / 山下 茂 / 中西 正樹[他]　(Suzuki, Tomoya / Yamashita, Shigeru / Nakanishi, Masaki)
　
22. 複雑形状を有する平面図形や空間図形に対する形状認識への複素関数論の応用(計算理論とアルゴリズムの新展開)-------------------------142
　　　　東京理科大学理工学部情報科学科　　　明石 重男
　
23. 文字列方程式における反復文字列(計算理論とアルゴリズムの新展開)-----------------------------------------------------------------147
　　　　真理大學資訊科學系　　　植村 仁
　
24. 価値科学と価値論理学の諸法則(計算理論とアルゴリズムの新展開)-------------------------------------------------------------------153
　　　　日本大学理工学部情報科学専攻&数学科　　　高橋 英之　(Takahashi, Hideyuki)
　
25. 3入出力2状態可逆論理素子の万能性 : ロータリー素子の直接的構成法(計算理論とアルゴリズムの新展開)--------------------------------160
　　　　広島大学大学院工学研究科 / 広島大学大学院工学研究科　　　上野 亮一 / 森田 憲一　(Ueno, Ryoichi / Morita, Kenichi)
　
26. 双符号形式による楕円曲線暗号系(計算理論とアルゴリズムの新展開)-----------------------------------------------------------------167
　　　　岡山大学大学院自然科学研究科 / 岡山大学大学院自然科学研究科 / 岡山大学大学院自然科学研究科　　　丁 峰 / 神保 秀司 / 橋口 攻三郎　(Ding, Feng / Jimbo, Shuji / Hashiguchi, Kosaburo)
　
27. Single Vehicle Scheduling Problem for Processing a Maximum Benefit Subset of Jobs on a Line(New Trends in Theory of Computation and Algorithm)---174
　　　　Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University / Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University　　　大西 隆治 / 永持 仁　(Ohnishi, Takaharu / Nagamochi, Hiroshi)
　
28. 2-Disjoint Path Covers in Mesh-Torus(New Trends in Theory of Computation and Algorithm)----------------------------------------181
　　　　東京工業大学大学院情報理工学研究科数理・計算科学専攻　　　牧野 格三　(Makino, Kozo)
　
29. 二段組合せ回路の最大動作率について(計算理論とアルゴリズムの新展開)-------------------------------------------------------------188
　　　　京都大学大学院情報学研究科 / 京都大学大学院情報学研究科 / 京都大学大学院情報学研究科　　　阿武 孝文 / 堀山 貴史 / 岩間 一雄　(ANNO, Takafumi / HORIYAMA, Takashi / IWAMA, Kazuo)
　
30. 紐解かれた項書換え系の文脈依存条件の除去のための変換(計算理論とアルゴリズムの新展開)-------------------------------------------195
　　　　名古屋大学工学部電気電子情報工学科 / 名古屋大学大学院情報科学研究科 / 名古屋大学大学院情報科学研究科　　　水谷 知博 / 西田 直樹 / 酒井 正彦[他]　(MIZUTANI, Tomohiro / NISHIDA, Naoki / SAKAI, Masahiko)
　
31. 拡張 Dyck 言語による TALs の特徴づけ(計算理論とアルゴリズムの新展開)-----------------------------------------------------------202
　　　　電気通信大学電気通信学研究科情報工学専攻　　　松原 俊一　(MATSUBARA, Shunichi)
　
32. 部分木のマッチを用いた構文解析木間の類似度について(計算理論とアルゴリズムの新展開)---------------------------------------------209
　　　　岡山理科大学大学院 / 岡山理科大学　　　秋友 克俊 / 椎名 広光　(Akitomo, Katsutoshi / Shiina, Hiromitsu)
　
33. 繰返し構造をもつラベル付順序木の簡潔な表現法(計算理論とアルゴリズムの新展開)---------------------------------------------------216
　　　　北海道大学 / 北海道大学 / 北海道大学　　　斉藤 智哉 / 中村 篤祥 / 工藤 峰一　(Saito, Tomoya / Nakamura, Atsuyoshi / Kudo, Mineichi)
　
34. 非同期分散システムにおける故障検知器と故障計数器について(計算理論とアルゴリズムの新展開)---------------------------------------223
　　　　九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学研究院 / 九州大学大学院システム情報科学研究院　　　坂田 敦 / 小野 廣隆 / 定兼 邦彦[他]　(Sakata, Atsushi / Ono, Hirotaka / Sadakane, Kunihiko)
　
35. センサーネットワークにおける省電力高信頼なデータ伝送(計算理論とアルゴリズムの新展開)-------------------------------------------229
　　　　九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学府　　　佐薙 光樹 / 小野 廣隆 / 定兼 邦彦[他]　(Sanagi, Koki / Ono, Hirotaka / Sadakane, Kunihiko)
　
36. 近傍探索の解合流性に基づく並列局所探索法の考察(計算理論とアルゴリズムの新展開)-------------------------------------------------233
　　　　九州大学大学院システム情報科学府 / 九州大学大学院システム情報科学研究院 / 九州大学大学院システム情報科学研究院 　　　半田 祐一 / 小野 廣隆 / 定兼 邦彦[他]　(Handa, Yuichi / Ono, Hirotaka / Sadakane, Kunihiko)
　
37. Coloring Comparability-ke Graphs(New Trends in Theory of Computation and Algorithm)--------------------------------------------239
　　　　電気通信大学情報工学科　　　武永 康彦　(Takenaga, Yasuhiko)
　
38. 正則グラフの1頂点を削除した部分グラフにおける 2-因子について(計算理論とアルゴリズムの新展開)-----------------------------------245
　　　　電気通信大学電気通信学研究科　　　木村 健司　(Kimura, Kenji)
　
39. The Confluence Problem for Flat TRSs(New Trends in Theory of Computation and Algorithm)----------------------------------------250
　　　　三重大学工学部 / 三重大学工学部 /　　　三橋 一郎 / 大山口 通夫 /　(Mitsuhashi, Ichiro / Oyamaguchi, Michio / Jacquemard, Florent)
　
40. 普遍代数における閉集合族と正データからの帰納推論(計算理論とアルゴリズムの新展開)-----------------------------------------------256
　　　　京都大学情報学研究科知能情報学専攻 / 首都大学東京 都市教養学部理工学系数理科学コース / 首都大学東京 都市教養学部理工学系数理科学コース　　　デ・ブレクト マシュー / 小林 正典 / 徳永 浩雄[他]　(de Brecht, Matthew / Kobayashi, Masanori / Tokunaga, Hiroo)
　
41. Polynomials Generating Minimal Clones on a Finite Field(New Trends in Theory of Computation and Algorithm)---------------------261
　　　　一橋大学　　　町田 元　(Machida, Hajime)