RIMS Kôkyûroku

No.1832

2012/09/12〜2012/09/14

鈴木　登志雄

Toshio Suzuki

目　次

1. 計算の複雑さと証明の複雑さ : 基調講演 (証明論と複雑性)----------------------------------------------------------------------------1

　　　　電気通信大学情報理工学研究科　　　垂井 淳　(Tarui,Jun)

　

2. A propositional proof system based on comparator circuits : 基調講演 (証明論と複雑性)--------------------------------------------2

　　　　群馬県立女子大学文学部　　　黒田 覚　(Kuroda,Satoru)

　

3. Sheaf-Theoretical Representation of Concrete Domains (Proof theory and complexity)------------------------------------------------8

　　　　法政大学経営学部　　　倉田 俊彦　(Kurata,Toshihiko)

　

4. 弱い2階算術におけるリーマンの写像定理 (証明論と複雑性)---------------------------------------------------------------------------19

　　　　米子工業高等専門学校　　　堀畑 佳宏　(Horihata,Yoshihiro)

　

5. 再帰的解析学における計算量 (証明論と複雑性)--------------------------------------------------------------------------------------33

　　　　 東京大学情報理工学系研究科　　　河村 彰星　(Kawamura,Akitoshi)

　

6. A Simplified Characterisation of Provably Computable Functions of the System ID$_1$ of Inductive Definitions : Extended Abstract (Proof theory and complexity)---39

　　　　東北大学理学研究科 / Department of Mathematics, Ghent University　　　江口 直日 / Weiermann Andreas　(Eguchi,Naohi / Weiermann,Andreas)

　

7. Bounded arithmetic in free logic (Proof theory and complexity)-------------------------------------------------------------------59

　　　　独立行政法人産業技術総合研究所　　　山形 頼之　(Yamagata,Yoriyuki)

　

8. On fine structures between Church-style and Curry-style $\lamnda$2-terms (Proof theory and complexity)---------------------------73

　　　　群馬大学工学部　　　藤田 憲悦　(Fujita,Ken-etsu)

　

9. Prawitz-Doorman Term Existence Property を超直観主義述語論理で考える (証明論と複雑性)--------------------------------------------88

　　　　静岡大学理学部数学教室　　　鈴木 信行　(SUZUKI,Nobu-Yuki)

　

10. 実数の集合論とランダムネス : 概説 (証明論と複雑性)------------------------------------------------------------------------------97

　　　　北陸先端科学技術大学院大学情報科学研究科　　　木原 貴行　(Kihara,Takayuki)

　

11. アルゴリズム的ランダムネスへの解析学的アプローチ (証明論と複雑性)--------------------------------------------------------------114

　　　　京都大学数理解析研究所　　　宮部 賢志　(MIYABE,KENSHI)

　

12. Notes on the first-order part of Ramsey's theorem for pairs (Proof theory and complexity)--------------------------------------127

　　　　東京工業大学情報理工学研究科　　　横山 啓太　(Yokoyama,Keita)

　

13. ラムダ計算と組み合わせ論理の体系C$\lambda$$I_\lambda$ (証明論と複雑性)---------------------------------------------------------135

　　　　千葉大学理学研究科基盤理学専攻 / 千葉大学理学研究科基盤理学専攻　　　山川 郁加 / 古森 雄一　(Yamakawa,Fumika / Komori,Yuichi)

　

14. 体系$C\lambda_I_\lambda$に関する予想の証明 (証明論と複雑性)--------------------------------------------------------------------139

　　　　千葉大学理学研究科基盤理学専攻　　　松田 直祐　(Matsuda,Naosuke)

　

15. Values on generalized reachability games (Proof theory and complexity)---------------------------------------------------------143

　　　　東北大学理学研究科 / 東北大学理学研究科 / 東北大学理学研究科　　　Ghani Ahmad Termimi Ab / 樋口 幸治郎 / 田中 一之　(Ghani,Ahmad Termimi Ab / Higuchi,Kojiro / Tanaka,Kazuyuki)

　

16. A Report on Studies of Relative Randomness (Proof theory and complexity)-------------------------------------------------------154

　　　　東北大学理学研究科　　　Peng,NingNing

　

17. 完全二分AND-OR木上の最適な乱択アルゴリズムについて (証明論と複雑性)------------------------------------------------------------158

　　　　首都大学東京理工学研究科数理情報科学専攻 / 首都大学東京理工学研究科数理情報科学専攻　　　仁井田 哲尚 / 小川 孝典　(Niida,Yoshinao / Ogawa,Kousuke)