No.1599

2008/01/28〜2008/01/30

渡辺　治

Osamu Watanabe

目　次

1. ストップウォッチオートマトンによるプリエンプティブスケジューリングの仕様記述と有界モデル検査 (理論計算機科学の深化 : 新たな計算世界観を求めて)---1

　　　　金沢大学自然科学研究科 / 金沢大学自然科学研究科　　　瀧内 新悟 / 山根 智　(Takinai, Shingo / Yamane, Satoshi)

　

2. DFAの極限学習における必要例数の解析 (理論計算機科学の深化 : 新たな計算世界観を求めて)---------------------------------------------9

　　　　東京工業大学情報理工学研究科数理計算科学専攻　　　林 賢史　(Hayashi, Kenji)

　

3. Local Structure of Cellular Automata (Foundations of Theoretical Computer Science : For New Computational View)------------------17

　　　　京都大学(元) /　　　西尾 英之助 /　(Nishio, Hidenosuke / Worsch, Thomas)

　

4. 70+.3rの法則 (理論計算機科学の深化 : 新たな計算世界観を求めて)-------------------------------------------------------------------24

　　　　山口大学工学部　　　伊藤 暁　(Ito, Akira)

　

5. 局所探索法による熱力学的DNA配列設計の改良 (理論計算機科学の深化 : 新たな計算世界観を求めて)--------------------------------------27

　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　川下 優 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Kawashimo, Suguru / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)

　

6. On Minimal Clones and Generating Polynomials (Foundations of Theoretical Computer Science : For New Computational View)----------35

　　　　一橋大学　　　町田 元　(Machida, Hajime)

　

7. ON CONCEPT LATTICE APPROXIMATION (Foundations of Theoretical Computer Science : For New Computational View)----------------------42

　　　　BERN UNIVERSITY OF APPLIED SCIENCES, ENGINEERING AND INFORMATION TECHNOLOGY　　　KWUIDA, LEONARD

　

8. 自明でない法則を用いた形式言語における概念分化 (理論計算機科学の深化 : 新たな計算世界観を求めて)---------------------------------50

　　　　真理大學数理學院資訊科學科　　　植村 仁　(Uemura, Jin)

　

9. 重み付きグラフ上の枝被覆に対する次数均等化と重み最小化 (理論計算機科学の深化 : 新たな計算世界観を求めて)-------------------------57

　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　原田 雄太 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Harada, Yuta / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)

　

10. Symmetricity of the Protocols Related to Oblivious Transfer (Foundations of Theoretical Computer Science : For New Computational View)---65

　　　　東京工業大学情報理工学研究科 / 東京工業大学情報理工学研究科　　　井上 大輔 / 田中 圭介　(Inoue, Daisuke / Tanaka, Keisuke)

　

11. グラフ上の線形Cover Timeランダムウォーク実現の必要条件 (理論計算機科学の深化 : 新たな計算世界観を求めて)------------------------73

　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　野中 良哲 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Nonaka, Yoshiaki / One, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)

　

12. Fixed point theorem on partial randomness (Foundations of Theoretical Computer Science : For New Computational View)------------79

　　　　中央大学研究開発機構　　　只木 孝太郎　(Tadaki, Kohtaro)

　

13. 4状態可逆チューリング機械の構成法 (理論計算機科学の深化 : 新たな計算世界観を求めて)---------------------------------------------86

　　　　広島大学工学研究科 / 広島大学工学研究科　　　森本 光也 / 森田 憲一　(Morimoto, Mitsuya / Morita, Kenichi)

　

14. しきい値回路のパターン数について (理論計算機科学の深化 : 新たな計算世界観を求めて)----------------------------------------------91

　　　　東北大学情報科学研究科 / 東北大学情報科学研究科　　　内沢 啓 / 瀧本 英二　(Uchizawa, Kei / Takimoto, Eiji)

　

15. $\mathrm{XOR}^2$=90 : Graded Algebra Structure of the Boolean Algebra of Local Transition Rules (Foundations of Theoretical Computer Science : For New Computational View)---97

　　　　九州工業大学情報工学部　　　藤尾 光彦　(FUJIO, Mitsuhiko)

　

16. Some Additional Remarks on Grammatical Characterizations of Alternating PDAs (Foundations of Theoretical Computer Science : For New Computational View)---103

　　　　早稲田大学教育学部 /　　　守屋 悦朗 /　(Moriya, Etsuro / Ott, Friedrich)

　

17. 疎フーリエ表現アルゴリズムの一実装 (理論計算機科学の深化 : 新たな計算世界観を求めて)-------------------------------------------111

　　　　長岡技術科学大学電気系 / 長岡技術科学大学電気系　　　八木谷 允 / 武井 由智　(YAGITANI, Masashi / TAKEI, Yoshinori)

　

18. 完全$k$分木のpath distance widthについて (理論計算機科学の深化 : 新たな計算世界観を求めて)-------------------------------------119

　　　　群馬大学工学研究科 / 群馬大学工学研究科 / 群馬大学工学研究科 / 群馬大学工学研究科 / 群馬大学工学研究科　　　受川 和幸 / 青木 一正 / 小澤 恭平 / 大舘 陽太 / 山崎 浩一　(Ukegawa, Kazuyuki / Aoki, Kazumasa / Kozawa, Kyohei / Otachi, Yota / Yamazaki, Koichi)

　

19. 局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)-------------------------------------127

　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　来見田 裕一 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Kurumida, Yuichi / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)

　

20. Gowers一様性による剰余関数と多項式の相関の評価 (理論計算機科学の深化 : 新たな計算世界観を求めて)-------------------------------133

　　　　東京工業大学数理・計算科学専攻 / 東京工業大学数理・計算科学専攻　　　田中 秀宗 / 河内 亮周　(Tanaka, Hidetoki / Kawachi, Akinori)

　

21. 3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて)----------141

　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　前村 一哉 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Maemura, Kazuya / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)

　

22. コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)-------------------148

　　　　京都大学数理解析研究所 / 北陸先端科学技術大学情報科学研究科 / 東京工業大学情報理工学研究科 / 国立情報学研究所　　　来嶋 秀治 / 清見 礼 / 岡本 吉央 / 宇野 毅明　(Kijima, Shuji / Kiyomi, Masashi / Okamoto, Yoshio / Uno, Takeaki)

　

23. Online Learning of Approximate Maximum $p$-Norm Margin Classifiers with Bias (Foundations of Theoretical Computer Science : For New Computational View)---154

　　　　九州大学システム情報科学府 / 九州大学システム情報科学府 / 九州大学システム情報科学府　　　石橋 浩介 / 畑埜 晃平 / 竹田 正幸　(Ishibashi, Kosuke / Hatano, Kohei / Takeda, Masayuki)

　

24. Notes on Enumeration of Concepts in a Sperner Family Concept Class Using Subconcept Queries (Foundations of Theoretical Computer Science : For New Computational View)---162

　　　　北海道大学情報科学研究科 / 北海道大学情報科学研究科　　　中村 篤祥 / 工藤 峰一　(Nakamura, Atsuyoshi / Kudo, Mineichi)

　

25. 確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察 (理論計算機科学の深化 : 新たな計算世界観を求めて)---170

　　　　九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　安藤 映 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Ando, Ei / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)

　

26. 多層型矩形分割に対する16分格子グラフ表現 (理論計算機科学の深化 : 新たな計算世界観を求めて)-------------------------------------176

　　　　日本大学総合基礎科学研究科 / 東洋大学工学部 / 日本大学文理学部　　　呉羽 彬 / 土田 賢省 / 夜久 竹夫　(Kureha, Akira / Tsuchida, Kensei / Yaku, Takeo)

　

27. 辺上を移動するロボット1台による最適な多角形探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)------------------------------182

　　　　九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　深見 浩和 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史　(Fukami, Hirokazu / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)

　

28. 正直なオークションにおける談合の影響 (理論計算機科学の深化 : 新たな計算世界観を求めて)-----------------------------------------189

　　　　京都大学情報学研究科 / 京都大学情報学研究科　　　市場 孝之 / 岩間 一雄　(Ichiba, Takayuki / Iwama, Kazuo)