1. 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)  
     
    My bibliography  
     
    Export citation  
  2. 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).
    Direct download  
     
    My bibliography  
     
    Export citation  
  3. 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 a proof is the number of lines (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation