ISSN 1880-2818

数理解析研究所講究録 1799

アルゴリズムと計算理論の新展開

京都大学数理解析研究所
2012 年 6 月

RIMS K\^okyuroku 1799

New Trends in Algorithms and Theory of Computation
January $30\sim February1$ , 2012edited by Keiichirou Kusakari

June, 2012

Research Institute for Mathematical Sciences
Kyoto University, Kyoto, Japan
This is a report of research done at the Research Institute for MathematicalSciences, Kyoto University. The papers contained herein are in final form
and will not be submitted for publication elsewhere.

アルゴリズムと計算理論の新展開
New Trends in Algorithms and Theory of Computation
RIMS 研究集会報告集
2012 年 1 月 30 日 $\sim 2$ 月 1 日研究代表者
平田 富夫 (Tomio Hirata)
目次

1. 完全マッチング数え上げの高速な指数時間アルゴリズムについて
名工大 (Nagoya Inst. Tech.)$————–1$

泉 泰介 (Taisuke Izumi)
和田山 正 (Tadashi Wadayama)//

2. Formula DecomPosition into Temary Majorities$——————————————13$
京大・次世代研究者育成センタ $=(KyotoU)$ 上野 賢哉 (Kenya Ueno)
3. Hybrid Automata Theoretic Specification and Verification of CPU-DRP$———-21$

Reconfigurable Systems
金沢大・自然科学 (Kanazawa U.)$\prime\prime$

柳瀬龍 ( $Ryo$ Yanase)高穎 (Gao Ying)

南〃

金沢大・理工研究域 (Kanazawa U.)

山根翔太 (Shota Minami)智 (Satoshi Yamane)

4. 抽象化洗練を用いた時間確率システムに対する形式的検証手法 $—————–29$
金沢大・自然科学 (Kanazawa U.)〃

5.

清水隆也 (Takaya Shimizu)森下
山根篤 (Atsushi Morimoto)金沢大・理工研究域 (Kanazawa U.)
智 (Satoshi Yamane)
セルオ $=$ トマトンの合成とリミットサイクルについて$————————–37$

九産大・基礎教育センタ $=$ (Kyushu Sangyo U.)
九大・数理学 (Kyushu U.)

6. 合同な四角形による球面タイリングの分類

石田

俊 $=$ (Toshikazu Ishida)井口修 $=$ (Shuichi Inokuchi)$—————44$

東北大・理学 (Tohoku U.)
赤間 陽二 (Yohji Akama)
国際協力機構 (JICA)
坂野 雄大 (Yudai Sakano)
東北大・理学 (Tohoku U.)
中村 公亮 (Kosuke Nakamura)
7. Variants of Petri net controlled grammars and their Parsing algorithms –49
富山県立大 (Toyama Pref. U.)
西田 泰伸(Taishin Yasunobu Nishida)

8. Relations between language classes in terms of insertion and locality $——————57$
九大・研究戦略企画室 (Kyushu U.)

9. 海草全単射の漸減構築
10.

藤岡薫 (Kaoru Fujioka)$——————————————–60$

東北大・農学 (Tohoku U.)
酒井 義文 (Yoshifumi Sakai)
アスペクト比を固定した最小の周囲長方形について $—————————65$
埼玉大工 (Saitama U.)
小林 有 (Tamotsu Kobayashi)
埼玉大理工学 (Saitama U.)
堀山 貴史 (Takashi Horiyama)$-$$i$$-$

$———————————————————-67$
太田 浩行 (Hiroyuki Ota)
東大・情報理工学系 (U. Tokyo)
河村 彰星 (Akitoshi Kawamura)Martin Ziegler
Tech. U. Darmstadt

11. 滑らかな常微分方程式の計算量

Carsten Rosnick$————————————73$
Quantum
ProofsShortwithTwo
12. On QMA Protocols
東大・情報理工学系 (U. Tokyo)
Fran\caois Le Gall
中川 翔太 (Shota Nakagawa)
大阪府大理学系 (Osaka Pref. U.)〃西村 治道 (Harumichi Nishimura)$———————————————-81$
13. Limiting Negations in Probabilistic Circuits
森住 大樹 (Hiroki Morizumi)
島根大・総合理工 (Shimane U.)
84
14. Greedy Algorithms for Multi-Queue Buffer Management with Class Segregation—

東工大・像情報工学研 (Tokyo Inst. Tech.)

伊東利哉 (Toshiya Ito)

東工大・情報理工学 (Tokyo Inst. Tech.)

吉本聖司 (Seiji Yoshimoto)

15. 格子グラフ上の最短経路問題のための劣線形領域アルゴリズム $—————–92$
東工大・情報理工学 (Tokyo Inst. Tech.)
東工大・理 (Tokyo Inst. Tech.)

今井達也 (Tatsuya Imai)

野口俊輔 (Shunsuke Noguchi)

藤〃16. GPU を用いた簡潔 trie の並列探索

哲郎 (Tetsuro Fuji)———————————————

JST田部井$=100$

靖生 (Yasuo Tabei)

田中 秀宗 (Hidetoki Tanaka)
東工大・情報理工学 (Tokyo Inst. Tech.)
17. Probabilistic Stabilization under Probabilistic Schedulers $——————————103$
山内 由紀子 (Yukiko Yamauchi)
九大・システム情報科学 (Kyushu U.)
S\’ebastien Tixeuil
Paris 6
山下 雅史 (Masahmi Yamashita)
九大・システム情報科学 (Kyushu U.)
18. ラベル選択付最小連結全域部分グラフ問題と化学構造式 OCR への応用 $—–111$
藤芳 明生 (Akio Fujiyoshi)
茨城大・工 (Ibaraki U.)

19.

九大・数理学 (Kyushu U.)
8 次格子モデルによる表の行/列操作

鈴木昌和 (Masakazu Suzuki)$—————————–118$

日大・文理 (Nihon U.)

高加晋司 (Shinji Koka)

電通大・情報理工学 (UEC)後藤隆彰 (Takaaki Goto)

東洋大・工 (Toyo U.)

土田

電通大・情報理工学 (UEC)
日大・文理 (Nihon U.)

西野賢省 (Kensei Tsuchida)
哲朗 (Tetsuro Nishino)

夜久

竹夫 (Takeo Yaku)

20. On the base-line location problem for the maximum weight region decomposable$——————————————————————-123$
堀山 貴史 (Takashi Horiyama)
埼玉大理工学 (Saitama U.)
伊藤 健洋 (Takehiro Ito)
東北大情報科学 (Tohoku U.)
小野 廣隆 (Hirotaka Ono)
九大経済学 (Kyushu U.)
大舘 陽太 (Yota Otachi)
東北大情報科学 (Tohoku U.)

into base-monotone shapes

北陸先端大・情報科学 (JAIST)上原隆平 (Ryuhei Uehara)

情報学研究所 (NII)宇野

毅明 (Takeaki Uno)$-$li$-$

21.

ランダムグラフ上の多種ランダムウォークの全訪問時間
九大・システム情報科学 (Kyushu U.)$————————130$
祐輔 (Yusuke Hosaka)
由紀子 (Yukiko Yamauchi)

穂坂〃

九大・経済学 (Kyushu U.)

山内
来嶋

秀治 (Shuji Kijima)

小野廣隆 (Hirotaka Ono)

九大・システム情報科学 (Kyushu U.)
山下 雅史 (Masafumi Yamashita)
22. Approximating Steiner Tree and Tree Cover Problems in Directed Graphs $———-137$
豊橋技科大 (Toyohashi U. Tech.)
日比 智也 (Tomoya Hibi)〃藤戸敏弘 (Toshihiro Fujito)

高田健司 (Kenji Takada)
一幸 (Kazuyuki Amano)$———145$

23. グラフの正方格子上への単位長配置について
群馬大工学 (Gunma U.)

天野

$/f$

24. Heuristic Algorithms for Rectilinear Block Packing
名大・情報科学 (Nagoya U.)〃

名大・工学 (Nagoya U.)
名大・情報科学 (Nagoya U.)$————————————153$
Yannan Hu
橋本 英樹 (Hideki Hashimoto)今堀 慎治 (Shinji Imahori)
柳浦 睦憲 (Mutsunori Yagiura)

25. グラフの頂点価格付け問題に対する実用的近似解法
東北大・情報科学 (Tohoku U.)

26.

$—————————–157$
坂紀 (Sakaki Nakamura)
昭義 (Akiyoshi Shioura)中村
塩浦

ストリ $=$ ム中の頻出アイテム発見に対する 0(loglogN り) り) 領域乱択

アルゴリズム$—————————–159$

九大・システム情報科学 (Kyushu U.)

正虎 (Masatora Ogata)緒方山内

由紀子 (Yukiko Yamauchi)

来嶋秀治 (Shuji Kijima)

山下雅史 (Masafumi Yamashita)

27. 距離遺伝 2 部グラフ上のハミルトン閉路アルゴリズム $—————————163$
名大情」
青報科学 (Nagoya U.)

高須賀

$|$

平田将秀 (Masahide Takasuka)
富夫 (Tomio Hirata)

28. 記憶付き可逆論理素子の能力の階層構造について $———————————167$
広島大・工学 (Hiroshima U.)$”$

向井優太 (Yuuta Mukai)

森田

憲 $=$ (Kenichi Morita)

29. mm-GNAT における分割点集合の選択手法に関する研究
東海大・理学 (Tokai U)

謝東海大・理 (Tokai U.)

大西

30. Automata inspired by biochemical reaction

建輔 (Kensuke Onishi)–179

早大・教育学 (Waseda U.)

31.

$———————–171$

評芳 (Pingfang Xie)

大久保

文哉 (Fumiya Okubo)

電通大・電気通信学 (UEC)
小林 聡 (Satoshi Kobayashi)
早大・教育・総合科学 (Waseda U.)
横森 貴 (Takashi Yokomori)
トリックテイキングゲームの計算量と必勝戦略 ————————————183
電通大情報理工学 (UEC)
中井 健一朗 (Kenichiro Nakai)
武永

$”$

$-$

$\ddot{u}i-$

康彦 (Yasuhiko Takenaga)

32. 連結文字列の圧縮長について$—–187$

東工大・情報理工学 (Tokyo Inst. Tech.)

遊佐俊彦 (Toshihiko Yusa)

33. 単位円交差グラフの線形構造を持つ部分クラスについて林

群馬大・工学 (Gunma U.)$———————–191$

貴史 (Takashi Hayashi)〃木野徹 (Toru Kino)〃

桑原勇人 (Yuto Kuwabara)〃

長澤亮介 (Ryosuke Nagasawa)

芝田
山崎悠華 (Yuka Shibata)〃

浩 $=$ (Koichi Yamazaki)

34. Pattem Formation by Fully Asynchronous Mobile Robots $——————————195$
九大・システム情報科学 (Kyushu U.)
〃

藤永
山内来嶋

〃

山下

〃

$-$lV

$-$

直 (Nao Fujinaga)
由紀子 (Yukiko Yamauchi)
秀治 (Shuji Kijima)
雅史 (Masafumi Yamashita)