２００６年１２月２０日作成

計算機科学の理論とその応用（冬の LA シンポジウム）
京都大学数理解析研究所の共同事業の１つとして、下記のように研究集会を催しますので、ご案内申し上げます。
研究代表者

16:40～18:00

セッション３

RIMS 研究集会

中野浩嗣（広島大学）

記
日時：２００７年１月２９日１２：５０～
２００７年１月３１日１２：２０
場所：京都大学数理解析研究所４２０号室[10] 根付きサイクル被覆問題に対するラグランジアン・ヒューリ
スティクス解法
羽田明生 (東北大学)[11] Approximation Algorithms for Maximum Triangle Packing
and Metric Maximum Clustering
陳 致中, 店橋 路可, ○関山 達之 (東京電機大学)[12] An Improved Approximation Algorithm for Maximum Edge
2-Coloring in Simple Graphs
陳 致中, ○店橋 路可 (東京電機大学)[13] エネルギー計算量に制限のあるしきい値論理回路について○内沢 啓, 瀧本 英二 (東北大学)

京都市左京区北白川追分町

1 月 30 日（火）1 月 29 日(月)オープニング(12:50～13:00)
セッション 1

9:00～10:20

セッション４13:00～14:40[14] フラクタル 2 次元立体のスウドク的色づけ
立木秀樹（京都大学）[1] 時間付き通信プロセスモデルにおける時間動作の抽象化○桑原 寛明, 結縁 祥治, 阿草 清滋 (名古屋大学)[15] 面積付き平面グラフに対する直交描画○川口 晃史, 永持 仁 (京都大学)[2] 正規パターン言語の積の正例からの学習とその計算量について植村 仁 (真理大学(中華民国))[16] 区間表現から MPQ-tree を構築するアルゴリズム○斎藤寿樹, 清見礼, 上原隆平 (北陸先端大学)[3] Alternating CFG の拡張について○守屋悦朗 (早稲田大学), Friedrich Otto, Hartmut
Messerschmidt (Universitat Kassel)[17] 負荷分散枝被覆問題に対する最適性とアルゴリズム○原田 雄太, 小野 廣隆, 定兼 邦彦, 山下 雅史 (九州大学)

セッション５[4] Neighborhood Function for CA○西尾英之助 (元・京大理学部), トーマス・ヴォルシュ (カールスルーエ大學)[5] Variations on neighborhoods in CA
トーマス・ヴォルシュ (カールスルーエ大學), ○西尾英之助 (元・京大理学部)

セッション２

15:00～16:20[6] 三部符号及び三部符号形式による RSA 暗号系○丁 峰, 神保 秀司, 橋口 攻三郎 (岡山大学)[7] 格子暗号の秘密鍵についての知識証明○草川恵太, 河内亮周, 田中圭介 (東京工業大学)[8] 集合被覆問題に関する近似アルゴリズムの秘匿性○八代 正俊, 田中 圭介 (東京工業大学)[9] アメリカン・アジアンオプションの価格付けに対する計算幾何手法を用いた近似アルゴリズム○渋谷 彰信, 徳山 豪, 塩浦 昭義 (東北大学)

10:40～12:00[18] Ptolemaic Graph 上の最長路問題に関する研究○高原 祥浩, 寺本 幸生, 上原 隆平 (北陸先端大学)[19] Quantum Asymmetric-Key Cryptosystems Secure Against
Computationally Unbounded Adversaries○Akinori Kawachi, Christopher Portmann (Tokyo Institute ofTechnology)[20] 量子回路計算量と制御 NOT ゲート数の関係について○大久保 誠也, 青木 輝人, 柿下 容弓, 西野哲朗 (電気通信大学)[21] Negation-Limited Complexity of Parity and Inverters○森住 大樹 (京都大学), 垂井 淳 (電気通信大学), 岩間 一雄 (京都大学)

セッション６13:00～14:00[22] 境界上を移動可能なロボット 2 台による多角形探索○深見浩和, 小野廣隆, 定兼邦彦, 山下雅史 (九州大学)[23] 3-正則グラフ上の行商人問題に対する厳密アルゴリズム○中島 拓也, 岩間一雄 (京都大学)

２００６年１２月２０日作成

1 月 31 日（水）[24] Montesinos 絡み目の Jones 多項式を計算するアルゴリズ
ムについて○村上 雅彦 (日本大学), 原 正雄 (東海大学), 山本 慎 (中央大学), 谷 聖一 (日本大学)

学生セッション１

14:20～15:50[25] Direct Binary Search 法によるマルチトニング○平野祐樹、中野浩嗣（広島大学）[26] Decidability of Innermost Termination for
Semi-Constructor Term Rewriting Systems○Keita Uchiyama, Masahiko Sakai, Naoki Nishida, Toshiki
Sakabe, Keiichirou Kusakari (Nagoya University)[27] Confluence of Length Preserving String Rewriting Systems
is Undecidable○王 誼, 酒井 正彦, 西田 直樹, 坂部 俊樹, 草刈 圭一朗(名古屋大学)[28] 高階項書換え系の定理自動証明に関する一考察○岡村 洋, 大山口 通夫, 山田 俊行 (三重大学)[29] 価値関数に基づいたソフトリアルタイムシステムのスケジューラ自動合成手法○加納 卓, 山根 智(金沢大学)[30] 述語抽象化精錬によるリアルタイムプログラムの自動検証手法○駒形龍太, 山根 智(金沢大学)

学生セッション２

16:10～17:25[31] 確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察(仮題)○安藤 映, 小野 廣隆, 山下 雅史 (九州大学)[32] DAG の高さを 4 以下に制限したタスクスケジューリングの近似アルゴリズムについて○清水 豪樹, 大山口 通夫, 山田 俊行, 柳本 貴之, 小松 健悟(三重大学)[33] 定数項の大きな線型しきい値関数に対する高速なオンライン学習○石橋浩介, 畑埜晃平, 竹田正幸 (九州大学)[34] 完全 2 分木に対する path distance width の下界○受川 和幸, 青木 一正, 小澤 恭平, 大舘 陽太, 山崎 浩一 (群馬大学)[35] Branchlength と Treelength○梅澤香織, 中澤直弘, 山崎浩一 (群馬大学)

EATCS Japan business meeting（17:25～17:55）
懇親会(18:30～)

セッション７9:00～10:40[36] ボトムアップ手法を用いた系統樹構築の近似アルゴリズム○前村一哉, 小野廣隆, 定兼邦彦, 山下雅史 (九州大学)[37] Simple Linear-Time Off-Line Text Compression byLongest-First Substitution○中村 亮介, 坂内 英夫, 稲永 俊介, 竹田 正幸 (九州大学)[38] 部分文字列の高速復元に適した圧縮データ構造に関する研究○後藤 隆元, 小野廣隆, 定兼邦彦, 山下雅史 (九州大学)[39] 局主探索法に基づく DNA 配列設計手法○川下 優, 小野廣隆, 定兼邦彦, 山下雅史 (九州大学)[40] 左線形項書換えシステムの合流性
岩見 宗弘 (島根大学)

セッション８11:00～12:20[41] センサーネットワークにおける省電力高信頼なデータ伝送○佐薙 光樹, 山下 雅史, 定兼 邦彦, 小野 廣隆 (九州大学)[42] Applying TrustRank on P2P Networks○米澤 弘毅, 田中 譲 (北海道大学)[43] k-set Agreement を解く故障検知器○坂田 敦, 小野廣隆, 定兼邦彦, 山下雅史 (九州大学)[44] 信用交渉における効率のよい戦略実行アルゴリズムについて○山本 有輝, 高田 喜郎, 関 浩之 (奈良先端大学)