ISSN 1880-2818

数理解析研究所講究録 1744

計算機科学とアルゴリズムの数理的基礎とその応用

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

RIMS $K\hat{o}k\gamma\hat{u}roku1744$

Mathematical Foundations and Applications ofComputer Science and A lgorithms
February 1

3, 2011$\sim$

edited by $Jun$ Tarui$June_{y}$2011Research 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.

計算機科学とアルゴリズムの数理的基礎とその応用
Mathematical Foundations and Applications of Computer Science and Algorithms
RIMS 研究集会報告集

201 1 年 2 月 1 日
研究代表者$\sim 2$月3日

哲朗 (Tetsuro Nishino)

西野目次

1. 実時間最終状態受理式決定性限定 1 カウンタ変換器の$——————————————————-1$多項式時間等価性判定アルゴリズム

電通大・情報理工学 (U. Electro-Communications)
光夫 (Mitsuo Wakatsuki)

若月
東芝ソリュ

$=$

ション (株) (Toshiba Solutions Corp.)

清野 和司 (Kazushi Seino)
電通大 (U. Electro-Communications)/ 中央大・研究開発機構 (Chuo U.)

富田

悦次 (Etsuji Tomita)

電通大・情報理工学 (U. Electro-Communications)西野

2. UML パッケージ図に対するグラフ文法
電通大・産学官連携センタ$=$

哲朗 (Tetsuro Nishino)$————————————————$–11(U. Electro-Communications)後藤隆彰 (Takaaki Goto)

電通大・情報理工学 (U. Electro-Communications)西野土田

3. 動的リアルタイムハイブリッド CEGAR
システムの設計検証

哲朗 (Tetsuro Nishino)

賢省 (Kensei Tsuchida)による動的再構成可能組込み

東洋大・工 (Toyo U.)

一————————————————————–

15

酒井 誠 (Makoto Sakai)
金沢大・自然科学 (Kanazawa U.)
金沢大・理工研究域 (Kanazawa U.)
山根 智 (Satoshi Yamane)
4. 確率時間 WiGAR による PTCTL サブクラスのモデル検査 $———————–25$
高橋 正樹 (Masaki Takahashi)
金沢大・自然科学 (Kanazawa U.)〃金沢大・理工研究域 (Kanazawa U.)

5.

ZDD によるパスの列挙

清水隆也 (Takaya Shimizu)

山根智 (Satoshi Yamane)$———————————————————————–35$
川原
斎藤純 (Jun Kawahara)

北大情報科学 (Hokkaido U.)
北大情報科学 (Hokkaido U.)/JST鈴木拡 (Hiromu Suzuki)
真一 (Shin-ichi Minato)(Hokkaido U.)

吉仲JST/ 北大情報科学(Hokkaido U.)〃JST/ 北大情報科学

湊

寿樹 (Toshiki Saitoh)

亮 (Ryo Yoshinaka)亮

6. Trevisan’s extractor in the presence of quantum side information –42
UC Berkeley
東工大・情報理工学 (Tokyo Inst. Tech.)
UC Berkeley

ETH Z\"urich$-$$i$$-$

Anindya De
Christopher Portmann
Thomas Vidick
Renato Renner7. UNO は一人でも難しい $————————————————————————48$
MIT

Erik D. Demaine
Martin L. Demaine

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

国立情報学研究所 (NII)
大阪府大理学系 (Osaka Pref. U.)

宇野毅明 (Takeaki Uno)

宇野裕之 (Yushi Uno)

8. 確率的評価値をもつゲーム木における最善手探索 $———————————–56$
九大システム情報科学 (Kyushu U.)

奥山畑埜

洋平 (Yohei Okuyama)

〃瀧本

〃

竹田

英二 (Eiji Takimoto)
正幸 (Masayuki Takeda)〃晃平 (Kohei Hatano)

9. Approximating the path-distance-width for -cocomparability graphs –60$k$

東北大情報科学 (Tohoku U.)

大舘JST

斎藤陽太 (Yota Otachi)
寿樹 (Toshiki Saitoh)

電通大・情報システム学 (U. Electro-Communications)
山中 克久 (Katsuhisa Yamanaka)
来嶋 秀治 (Shuji Kijima)
九大システム情報科学 (Kyushu U.)
北陸先端大大学院教育イニシアティブセンター (JAIST)岡本 吉央 (Yoshio Okamoto)小野 廣隆 (Hirotaka Ono)
九大経済学 (Kyushu U.)
宇野 裕之 (Yushi Uno)
大阪府大理学系 (Osaka Pref. U.)
山崎 浩一 (Koichi Yamazaki)
群馬大工学 (Gunma U.)
10. Approximating Maximum Edge 2-Coloring in Simple Graphs $————————-67$
東京電機大理工 (Tokyo Denki U.)
Zhi-Zhong Chen
今野 さゆり (Sayuri Konmo)
東京電機大理工学 (Tokyo Denki U.)〃松下 裕希 (Yuki Matsushita)
1 1. Universality of Reversible Logic Elements with 1-Bit Memory (Extended Abstract) $—77$
森田 憲一 (Kenichi Morita)
広島大工学 (Hiroshima U.)

荻路〃

剛 (Tsuyoshi Ogiro)

広島大工学 (Hiroshima U.)/Acad. Sci. Moldova

Artiom Alhazov
広島大工学 (Hiroshima U.)

12.

谷沢 剛 (Tsuyoshi Tanizawa)
2 次の効用関数を持つ不可分財の最適配分問題に対する近似解法の研究 $—–85$
鈴木 瞬也 (Shunya Suzuki)
東北大情報科学 (Tohoku U.)

塩浦〃

13. タブローの最適配置問題

昭義 (Akiyoshi Shioura)$———————————————-93$

東北大情報科学 (Tohoku U.)

安齋全

葛西

〃

U. Libre Bmxelles

進也 (Shinya Anzai)
眞嬉 (Jinhee Chun)
亮生 (Ryosei Kasai)

コルマン

マティアス(Matias Korman)

東北大情報科学 (Tohoku U.)

徳山-

11-

豪 (Takeshi Tokuyama)

14. 組合せの効率的な生成法

99

$———$

京大情報学 (Kyoto U.)

清水俊宏 (Toshihiro Shimizu)

福永 拓郎 (Takuro Fukunaga)
永持 仁 (Hiroshi Nagamochi)
15. 最長共通部分配列計算における mn 長の対数時間寄与 $—————————–107$
東北大・農学 (Tohoku U)
酒井 義文 (Yoshifumi Sakai)
16. A Searchable Compressed Edit-Sensitive Parsing $—————————————–115$
九工大情報工学 (Kyushu Inst. Tech.)
岸上 直也 (Naoya Kishiue)
$”$

$”$

中原 昌也 (Masaya Nakahara)
丸山 史郎 (Shirou Maruyama)
九大システム情報科学 (Kyushu U.)
九工大情報工学 (Kyushu Inst. Tech.)/JST 坂本 比呂志 (Hiroshi Sakamoto)
圧縮文字列上での -gram 頻度の高速な計算方法 $———————————–123$
〃

17.

$q$

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

啓介 (Keisuke Goto)

坂内
稲永
竹田英夫 (Hideo Bannai)
俊介 (Shunsuke Inenaga)
正幸 (Masayuki Takeda)

18. Dynamic Programming Algorithm for Optimal Double-Base Chains(Extended Abstract)$——————————————————————-$129

東大・情報理工学系 (U. Tokyo)/JST
Vorapong Suppakitpaisam
NEC Corp. / 東大・情報理工学系 (U. Tokyo) 枝廣 正人 (Masato Edahiro)
東大・情報理工学系 (U. Tokyo)/JST

今井浩 (Hiroshi Imai)

19. Local Composition of Cellular Automata via Hit-or-Miss Transform –137
九工大・情報工学 (Kyushu Inst. Tech.)

藤尾光彦 (Mitsuhiko Fujio)

20. Cancel minimal linear grammars with a Particular nonterminal symbol –144

21.

九大・研究戦略企画室 (Kyushu U.)
藤岡 薫 (Kaom Fujioka)
東京電機大・理工 (Tokyo Denki U.)
勝野 裕文 (Hirofumi Katsuno)
Degree sequences related to degree set (extended abstract) –151
群馬大・工学 (Gunma U.)
大澤 新吾 (Shingo Osawa)
柴田幸夫 (Yukio Shibata)

22. いかなる辺展開でも正多面体は重なりを持たない $———————————-159$
埼玉大・理工学 (Saitama U.)堀山

貴史 (Takashi Horiyama)

庄子

亘 (Watam Shoji)

23. 木オートマトンを用いた化学グラフのスクリー- ニング手法 $——————-161$
茨城大・工 (Ibaraki U.)藤芳

24. 最大クリーク問題の多項式時間的可解性について

明生 (Akio Fujiyoshi)$———————————169$

電通大・先進アルゴリズム (U. Electro-Communications)
中西

裕陽 (Hiroaki Nakanishi)

電通大・先進アルゴリズム (U. Electro-Communications)/
中央大研究開発機構 (Chuo U.)
富田 悦次 (Etsuji Tomita)
電通大先進アルゴリズム / 情報理工学 (U. Electro-Communications)
若月 光夫 (Mitsuo Wakatsuki)
西野 哲朗 (Tetsuro Nishino)$”$

一垣1$-$

25. 最急上昇法による尾根抽出
日大・文理 (Nihon U.)$——–177$$”$26.

高加晋司 (Shinji Koka)

野牧賢志 (Kenshi Nomaki)

杉田 公生 (Kimio Sugita)
東海大・理 (Tokai U.)
土田 賢省 (Kensei Tsuchida)
東洋大・工 (Toyo U.)
夜久 竹夫 (Takeo Yaku)
日大・文理 (Nihon U.)
量子セルオ $=$ トマトンに基づく画像圧縮のための画像変換アルゴリズム $—-181$

電通大・情報理工学 (U. Electro-Communications)大畑
西野

若月和樹 (Kazuki Oohata)
哲朗 (Tetsuro Nishino)
光夫 (Mitsuo Wakatsuki)

27. Image Recognition and Retrieval by Using Distance Information $———————185$
東北大・情報科学 (Tohoku U.)

全眞嬉 (Jinhee Chun)’/

Natsuda Kaothanthong〃

徳山豪 (Takeshi Tokuyama)

28. AKS 素数判定アルゴリズムについての計算機を用いた実験的考察
岡山大自然科学 (Okayama U.)
〃

29.

難波神保

秀司 (Shuji Jimbo)$—————————————193$

線形刻み幅の双対定理について

群馬大・工学 (Gunma U.)’/$\prime\prime$30.

$———189$

雄策 (Yusaku Nanba)

片平明 (Akira Katahira)

桑原長澤大舘山崎勇人 (Yuto Kuwabara)

亮介 (Ryosuke Nagasawa)
陽太 (Yota Otachi)

東北大・情報科学 (Tohoku U.)
浩一 (Koichi Yamazaki)
群馬大・工学 (Gunma U.)
非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム $—————————————————————-197$
藤永 直 (Nao Fujinaga)
九大システム情報科学 (Kyushu U.)
小野 廣隆 (Hirotaka Ono)
九大経済学 (Kyushu U.)
来嶋 秀治 (Shuji Kijima)
九大・システム情報科学 (Kyushu U.)〃山下 雅史 (Masafumi Yamashita)

31. 大規模分散フレームワーク Hadoop を用いた接尾辞配列構築$—————–201$

洋輔 (Yosuke Tanaka)

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

田中

国立情報学研究所 (NII)

定兼

邦彦 (Kunihiko Sadakane)

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

山下雅史 (Masafumi Yamashita)

32. ストリーミング中の頻出アイテム発見アルゴリズム $——————————–205$緒方

正虎 (Masatora Ogata)〃来嶋秀治 (Shuji Kijima)〃山下

雅史 (Masafumi Yamashita)

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

33. 文法圧縮に基づいた圧縮データの自己索引構造化の提案
九大・システム情報科学 (Kyushu U.)

馬場
丸山

〃

九工大情報工学 (Kyushu Inst. Tech.)

坂本

国立情報学研究所 (NII)

定兼

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

山下

$-$

IV

$-$$————————209$

雅大 (Masahiro Baba)
史郎 (Shirou Mamyama)
比呂志 (Hiroshi Sakamoto)
邦彦 (Kunihiko Sadakane)
雅史 (Masafumi Yamashita)34. センサネットワーク上の群生成による情報伝達 $———————————-213$
東京電機大工学 (Tokyo Denki U.)
〃35.

中山

弾作 (Dansaku Nakayama)

坂本直志 (Naoshi Sakamoto)広島大・工学 (Hiroshima U.)
今井 克暢 (Katsunobu Imai)
仮想世界上での近距離合意問題 $———————————————————-217$
東京電機大工学 (Tokyo Denki U.)
榎本 慎太郎 (Shintaro Enomoto)-V