On lengths of proofs in propositional calculi 命題論理における証明の長さの研究

この論文をさがす

著者

    • 新井, 紀子 アライ, ノリコ

書誌事項

タイトル

On lengths of proofs in propositional calculi

タイトル別名

命題論理における証明の長さの研究

著者名

新井, 紀子

著者別名

アライ, ノリコ

学位授与大学

東京工業大学

取得学位

博士 (理学)

学位授与番号

乙第3021号

学位授与年月日

1997-03-31

注記・抄録

博士論文

目次

  1. 論文目録 / (0002.jp2)
  2. Contents / p2 (0005.jp2)
  3. 1 Introduction / p3 (0006.jp2)
  4. 1.1 Cut-elimination and lengths of propositional calculi / p3 (0006.jp2)
  5. 1.2 Automatic theorem proving and the lengths of proofs / p4 (0007.jp2)
  6. 1.3 Complexity class, bounded arithmetic and propositional calculus / p5 (0008.jp2)
  7. 2 A proper hierarchy of propositional sequent calculi / p9 (0012.jp2)
  8. 2.1 Preliminaries / p10 (0013.jp2)
  9. 2.2 Systems of propositional calculus / p11 (0014.jp2)
  10. 2.3 Exponential effects of cut-elimination on lengths of proofs / p15 (0018.jp2)
  11. 2.4 Further related results and conclusions / p26 (0029.jp2)
  12. 2.5 Cut-elimination theorem for first-order predicate calculus / p28 (0031.jp2)
  13. 2.6 Appendix:bounded depth LK vs.LKn / p36 (0039.jp2)
  14. 3 Tractability of cut-free Gentzen style propositional calculus with permutation inference / p44 (0047.jp2)
  15. 3.1 Gentzen system GCXF / p44 (0047.jp2)
  16. 3.2 Relative efficiency of GCNF and GCXF+permutation / p45 (0048.jp2)
  17. 3.3 Polynomial-size proofs of PHPn and k-Eqո / p51 (0054.jp2)
  18. 3.4 The consistency of Frege+renaming / p57 (0060.jp2)
  19. 4 Bounded arithmetic vs.propositional calculus / p62 (0065.jp2)
  20. 4.1 The system[数式] / p63 (0066.jp2)
  21. 4.2 Translation of[数式]proofs to polynomial-size extended Frege proofs / p67 (0070.jp2)
  22. 4.3 Main theorem / p73 (0076.jp2)
  23. 4.4 Translation of other bounded arithmetic to propositional calculi / p79 (0082.jp2)
19アクセス

各種コード

  • NII論文ID(NAID)
    500000153891
  • NII著者ID(NRID)
    • 8000001092905
  • DOI(NDL)
  • NDL書誌ID
    • 000000318205
  • データ提供元
    • NDL-OPAC
    • NDLデジタルコレクション
ページトップへ