Switch to: References

Add citations

You must login to add citations.
  1. On the correspondence between arithmetic theories and propositional proof systems – a survey.Olaf Beyersdorff - 2009 - Mathematical Logic Quarterly 55 (2):116-137.
    The purpose of this paper is to survey the correspondence between bounded arithmetic and propositional proof systems. In addition, it also contains some new results which have appeared as an extended abstract in the proceedings of the conference TAMC 2008 [11].Bounded arithmetic is closely related to propositional proof systems; this relation has found many fruitful applications. The aim of this paper is to explain and develop the general correspondence between propositional proof systems and arithmetic theories, as introduced by Krajíček and (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Lower complexity bounds in justification logic.Samuel R. Buss & Roman Kuznets - 2012 - Annals of Pure and Applied Logic 163 (7):888-905.
    Download  
     
    Export citation  
     
    Bookmark  
  • Generalisation of proof simulation procedures for Frege systems by M.L. Bonet and S.R. Buss.Daniil Kozhemiachenko - 2018 - Journal of Applied Non-Classical Logics 28 (4):389-413.
    ABSTRACTIn this paper, we present a generalisation of proof simulation procedures for Frege systems by Bonet and Buss to some logics for which the deduction theorem does not hold. In particular, we study the case of finite-valued Łukasiewicz logics. To this end, we provide proof systems and which augment Avron's Frege system HŁuk with nested and general versions of the disjunction elimination rule, respectively. For these systems, we provide upper bounds on speed-ups w.r.t. both the number of steps in proofs (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Some remarks on lengths of propositional proofs.Samuel R. Buss - 1995 - Archive for Mathematical Logic 34 (6):377-394.
    We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m d+1) symbols. We show that renaming (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations