ISSN 1880-2818
数理解析研究所講究録 1599
理論計算機科学の深化 : 新たな計算世界観を求めて
京都大学数理解析研究所
2008 年 5 月
RIMS K6/¡yOroku Z599
,Foundations of 772eoretical Computer S ℃ ience.e For New Computational l7iew
imy, 2008
Research Instztute for Mlathematzcal Sciences
Kyoto Ujeiverszty, K)2oto, .lapan
This is a report of research done at Research Institute fbr Mathematrcal Sciences, Kyoto University The papers contamed herem are m final form
and wdl not be submitted for publication elsewhere
理論計算機科学の深化 新たな計算世界観を求めて
Foundations of Theoretical Computer Science For New Computational View RIMS研究集会報告集
2008年1月28日{}˜1月30日
研究代表者 渡辺 治(Osamu Watanabe)
目 次
1ストノブウォソチオートマトンによるプリエンプティブスケジューーリングの 仕様記述と有界モデル検査
金沢大・自然科学(Kanazawa・U)
!1
2 DFAの極限学習における必要例数の解析 東工大・情報理工学(Tokyo Inst Tech)
3 Local Structure of Cellular Automata
元・京大(Kyoto U) U Karlsmbe
瀧内 新悟(Shmgo Takmai) 山根 智(Satoshl Yamane)
1
林 賢史(KenJ1 Hayashi)
9
4 70+3rの法則
西尾 英之助(Hidenosuke・Nlshlo) Thomas Worsch
17
5
6 7
8
910
24 山回大・工(YamagUchi U) 伊藤 暁(Akmra Ito)
局所探索法による熱力学的DNA配列設計の改良 一・一・一・一・一一一一…一一一・一一一…一一一一27 九大・システム情報科学(Kyushu U)川下 優(Suguru Kawashlmo)
小野 廣隆 (Hirotaka Ono)
〃 定兼 邦彦 (Kun 血 ko Sadakane)
〃 山下 雅史 (MasafUml Yamashlta) On Mlmmal Clones and Generatmg Polynomlals一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一35
一一橋大・商学(HltotSubashn・U) 町田 元(HaJ rme Machida)
ON CONCEPT LArnCE APPROXIMATION 一一 ・一一一一m 一 ・・ 一一一 一 一一一e一e一 … b 一 t 一m 42
Bern U Applied Sci Leonard Kwuida
自明でない法則を用いた形式言語における概念分化・一・…一一e一・・一一一e-e一一・・一一・一一50 真理大(Alethela U) 植村 仁(Jm・Uamura)
重み付きグラフ上の枝被覆に対する次数均等化と重み最小化.. .一。一。一一一 ..57 九大・システム情報科学(Kyushu U)原田 雄太(Yuta・Harada)
〃 小野 二二 (Hrrotaka Ono)
〃 定兼 邦彦 (Kun 血 iko Sadakme)
〃 山下 雅史 (MasafUmi Yamash lta) Symmetnclty of 1血e Protocols Related to Obllvlous Transfbr一■… .一一.pee-r一・一一一・●●一・・… 一e■・65
東工大・情報理工学(Tokyo Inst Tech) 井上 大輔(Dalsuke Inoue) 田中 圭介 (KelsUke・Tana:km)
欄1一
11
12 13
14
15
16
17
18
群馬大・工学(Gunma U)
11 11
1r 11
19局所的な次数情報を用いた無向グラフの探索 九大・システム情報科学(Kyushu U)
Il 1I lt
グラフ上の線形Cover・Trmeランダムウォーーク実現の必要条件 一eee一一一一el-t-vtt J一一一一一 73 九大・システム情報科学(Kyushu u)野中 良哲(Yoshlak1 Nona:km)
〃 小野 廣隆 (Hrrotaka Ono)
〃 定書 邦彦 (Kun 血ko sadakane)
〃 山下 雅史 (MasaftUni Yamasluta) FIXed poMt thcoren1 On Panlal randomness 一一一一一一 一・ 一・一・・e・一 一・一一一一一一一一n一一一一一一一一一一一一一一一一一 一79
中央大・研究開発機構(Chuo U)只木 孝太郎(Kohtaro Tada:k1)
4 状態可逆チューリング機械の構成法 86
広島大・工学(Hrroshlma・U)森本 光也(Mitsuya Mommoto)
〃 森田 憲一 (KenlckmMonta)
On Patterns of Threshold Crrcuits computmg the PARITY fUnction一一一一一一一一一一一一一一一一…一一一一91 東北大・情報科学(Tohoku U) 内沢 啓(Ke1 Uchlzawa)
〃 瀧本 英二 (E η 1 Takimoto)
xoR2=90
Graded Algebra Structure of the Boolean Algebra of Local TransMon Rules一一一一97 九工大・情報工(Kyushu lnst Tech) 藤尾 光彦(Mitsuhiko FuJio)
Some Addmonal Remarks on Grammancal Charactenzations of Alternatmg PDAs一一一103 早大・教育(Waseda・U) 守屋 悦朗(EtSuro Monya)
UKassel Fnednch Otto
疎フー Vh一リエ表現アルゴリズムの一実装 111 長岡技術科学大(Nagaoka U Tech)八木谷 允(Masash1 Yagltani)
〃 武井 由智 (Yoshmon Take1) 完全k 分木のpath dlstance wld血について ・・ … l19
川木澤舘崎
受青小大山
和幸(Kazuyuki Ukegawa)一正(Kazumasa Aoki) 恭平(Kyohel Kozawa) 陽太(Yota Otach1) 浩一(Kolch1 Yamazaki)
eeee一一D一一一e-e一一一e-ewe一127
来見田 裕一(YUichi Kurumlda) 小野 廣隆(Hrrotaka・Ono) 定兼 邦彦(Kunthiko sadakane) 山下 雅史(MasafUmi YamastUta) 20 Gowers一様性による剰余関数と多項式の相関の評価
東工大・情報理工学(Tokyo Ihst Tech) 田中
〃 河内
e-e一一em-eee一 一eeee-eeeeeeee-eee一133
秀宗(Hldetoki Tanaka) 亮周(Akmon Kawach1)
一一11
21
22
23
24
25
26
27
28
3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析141 九大 ンステム情報科学(Kyushu U)前村 一哉(Kazuya Maenura)
小野 面出 (Hrrota:ka Ono)
〃 虚血 邦彦(Ku 血 hiko Sadakane)
〃 山下 雅史(MasafUmi Yamaslnta) コーダルサンドイノチの列挙,ランダム生成,数え上げについて …・一一。一一148
京大 数理研(Kyoto U) 来嶋 秀治(ShUJ I KIJ Ima) 北陸先端大 情報科学(JAIST) 清見 礼(Masash1 Klyom1) 東工大・情報理工学(Tokyo lnst Tech)岡本吉央(Yoslllo Okamoto) 国立情報学研究所(Nat Inst Informatlcs)宇野 盆明(Takeak1 Uno)
Onlme Learnmg of Approxrmate Maxrmum p Norm Margm Classifiers wmb Basis 154 九大 ンステム情報科学(Kyushu U)石橋 浩介(Kosuke Ishlbash1)
〃 畑埜 晃平 (Kohe1 Hatano)
〃 竹田 正幸 (MasayUk1 Ta:keda) Notes on Enumeration of Concepts m a Sperner Family
Concept Class Usmg Subconcept Quenes一 一 一 一 一一 一一 一 一 一一一一 一一一一162 北大 情報科学(Hokkaldo U)中村 血止(AtSuyoshi Nakarnura)
〃 工藤 峰一一 (Mlnelchl Kudo) 確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの
分布関数の解析的な計算に関する考察 170
九大 ンステム情報科学(Kyushu U) 安藤 映(Ei Ando)
〃 小野 白血 (Hrrotaka・Ono)
〃 面面 邦彦 (Kun 血 ko Sadakane)
〃 山下 雅史(MasafUmi・Yamashlta) 多層型矩形分割に対する 16分格子グラフ表現 176
日大 総合基礎科学(N血on・U)呉羽 彬(Akma Kureha) 東洋大 工(Toyo U) 土田 賢省(Kense1・Tsuchlda)
日大 文理(Nlhon U) 夜久 竹夫(Takeo Yaku)
辺上を移動するロポノト1台による最適な多角形探索 ……・一… 一一一182 九大・ンステム情報科学(Kyushu U)深見 浩和(Hrrokazu FUIvami)
〃 小野 虚血 (Hrrotaka・Ono)
〃 定心 邦彦 (Kunthrko sadakane)
〃 山下 雅史 (Masaf m1 Yamashlta) 正直なオークンヨンにおける談合の影響 189
京大・情報学(Kyoto U) 市場 孝之(Takayuk1 lchiba)
〃 岩間 一雄 (Kazuo Iwama)
一m一
