1.  17
    Maria Luisa Bonet & Samuel R. Buss (1993). The Deduction Rule and Linear and Near-Linear Proof Simulations. 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 (...)
    Direct download (6 more)  
    Export citation  
    My bibliography   2 citations  
  2.  9
    Maria Luisa Bonet & Nicola Galesi (2003). Degree Complexity for a Modified Pigeonhole Principle. Archive for Mathematical Logic 42 (5):403-414.
    No categories
    Direct download (4 more)  
    Export citation  
    My bibliography  
  3.  3
    Julia Knight, Nest Priority Constructions, Maria Luisa Bonet & On Finding Hard Tautologiesfor Frege (1995). 1994 Annual Meeting of the Association for Symbolic Logic. Bulletin of Symbolic Logic 1 (1):377-389.
    Direct download  
    Export citation  
    My bibliography