On lengths of proofs in propositional calculi 命題論理における証明の長さの研究
この論文にアクセスする
この論文をさがす
著者
書誌事項
- タイトル
-
On lengths of proofs in propositional calculi
- タイトル別名
-
命題論理における証明の長さの研究
- 著者名
-
新井, 紀子
- 著者別名
-
アライ, ノリコ
- 学位授与大学
-
東京工業大学
- 取得学位
-
博士 (理学)
- 学位授与番号
-
乙第3021号
- 学位授与年月日
-
1997-03-31
注記・抄録
博士論文
目次
- 論文目録 / (0002.jp2)
- Contents / p2 (0005.jp2)
- 1 Introduction / p3 (0006.jp2)
- 1.1 Cut-elimination and lengths of propositional calculi / p3 (0006.jp2)
- 1.2 Automatic theorem proving and the lengths of proofs / p4 (0007.jp2)
- 1.3 Complexity class, bounded arithmetic and propositional calculus / p5 (0008.jp2)
- 2 A proper hierarchy of propositional sequent calculi / p9 (0012.jp2)
- 2.1 Preliminaries / p10 (0013.jp2)
- 2.2 Systems of propositional calculus / p11 (0014.jp2)
- 2.3 Exponential effects of cut-elimination on lengths of proofs / p15 (0018.jp2)
- 2.4 Further related results and conclusions / p26 (0029.jp2)
- 2.5 Cut-elimination theorem for first-order predicate calculus / p28 (0031.jp2)
- 2.6 Appendix:bounded depth LK vs.LKn / p36 (0039.jp2)
- 3 Tractability of cut-free Gentzen style propositional calculus with permutation inference / p44 (0047.jp2)
- 3.1 Gentzen system GCXF / p44 (0047.jp2)
- 3.2 Relative efficiency of GCNF and GCXF+permutation / p45 (0048.jp2)
- 3.3 Polynomial-size proofs of PHPn and k-Eqո / p51 (0054.jp2)
- 3.4 The consistency of Frege+renaming / p57 (0060.jp2)
- 4 Bounded arithmetic vs.propositional calculus / p62 (0065.jp2)
- 4.1 The system[数式] / p63 (0066.jp2)
- 4.2 Translation of[数式]proofs to polynomial-size extended Frege proofs / p67 (0070.jp2)
- 4.3 Main theorem / p73 (0076.jp2)
- 4.4 Translation of other bounded arithmetic to propositional calculi / p79 (0082.jp2)
