4 found
  1.  30
    The Deduction Rule and Linear and Near-Linear Proof Simulations.Maria Luisa Bonet & Samuel R. Buss - 1993 - Journal of Symbolic Logic 58 (2):688-709.
    We introduce new proof systems for propositional logic, simple deduction Frege systems, general deduction Frege systems, and nested deduction Frege systems, which augment Frege systems with variants of the deduction rule. We give upper bounds on the lengths of proofs in Frege proof systems compared to lengths in these new systems. As applications we give near-linear simulations of the propositional Gentzen sequent calculus and the natural deduction calculus by Frege proofs. The length of a proof is the number of lines (...)
    Direct download (7 more)  
    Export citation  
    Bookmark   3 citations  
  2.  9
    Degree Complexity for a Modified Pigeonhole Principle.Maria Luisa Bonet & Nicola Galesi - 2003 - Archive for Mathematical Logic 42 (5):403-414.
    No categories
    Direct download (4 more)  
    Export citation  
  3.  3
    Quasipolynomial Size Frege Proofs of Frankl’s Theorem on the Trace of Sets.James Aisenberg, Maria Luisa Bonet & Sam Buss - 2016 - Journal of Symbolic Logic 81 (2):687-710.
  4.  4
    1994 Annual Meeting of the Association for Symbolic Logic.Julia Knight, Nest Priority Constructions, Maria Luisa Bonet & On Finding Hard Tautologiesfor Frege - 1995 - Bulletin of Symbolic Logic 1 (1):377-389.