The deduction rule and linear and near-linear proof simulations

DOI10.2307/2275228zbMath0848.03028OpenAlexW2012084714MaRDI QIDQ3138022

Maria Luisa Bonet, Samuel R. Buss

Publication date: 24 October 1993

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275228

zbMATH Keywords

natural deduction calculusspeedupFrege systemslength of proofsproof systems for propositional logicnear-linear simulationspropositional Gentzen sequent calculustree-like systemsvariants of the deduction rule

Mathematics Subject Classification ID

Proof theory in general (including proof-theoretic semantics) (03F03) Complexity of proofs (03F20)

Related Items

Some remarks on lengths of propositional proofs, Logical Closure Properties of Propositional Proof Systems, Lower complexity bounds in justification logic, Generalisation of proof simulation procedures for Frege systems by M.L. Bonet and S.R. Buss, Exponential lower bounds for the pigeonhole principle, The deduction theorem for strong propositional proof systems, Simulation of Natural Deduction and Gentzen Sequent Calculus, The NP-Completeness of Reflected Fragments of Justification Logics, The Deduction Theorem for Strong Propositional Proof Systems, On the correspondence between arithmetic theories and propositional proof systems – a survey

Cites Work

• The relative efficiency of propositional proof systems
• Unnamed Item
• Unnamed Item