scientific article; zbMATH DE number 65760

MaRDI QIDQ4010371zbMATH OpenFDO

Authors Alasdair Urquhart

Publication date 27 September 1992

zbMATH Keywords

surveyclassical propositional logiccomplexity of proofspropositional proof systemsResolution\(p\)-simulationCut-free Gentzen systemsExtended Frege systemsFixed-depth Frege systemsQuantified Frege systemsTruth tables

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Classical propositional logic (03B05) Complexity of proofs (03F20)

Recommendations

• The Complexity of Propositional Proofs
• Proof theory
• scientific article; zbMATH DE number 1860672
• Relative efficiency of a proof system for classical propositional logic
• On the relative efficiency of different systems for classical and nonclassical propositional logics

Cited in

(26)

• ON THE CLASSIFICATION OF PROPOSITIONAL PROVABILITY LOGICS
• A proper hierarchy of propositional sequent calculi
• The polynomial bounds of proof complexity in Frege systems
• scientific article; zbMATH DE number 1860652 (Why is no real title available?)
• On the modal logic K plus theories
• Are tableaux an improvement on truth-tables? Cut-free proofs and bivalence
• scientific article; zbMATH DE number 4114609 (Why is no real title available?)
• The Complexity of Propositional Proofs
• Complexity Classifications for Logic-Based Argumentation
• Reduction of Hilbert-type proof systems to the if-then-else equational logic
• From multiple sequent for additive linear logic to decision procedures for free lattices
• On proof normal forms for some systems of classical propositional logic
• On the relative efficiency of different systems for classical and nonclassical propositional logics
• Relative efficiency of a proof system for classical propositional logic
• scientific article; zbMATH DE number 937363 (Why is no real title available?)
• On the proof complexity of logics of bounded branching
• Expressing versus proving: relating forms of complexity in logic
• Upper bounds on complexity of Frege proofs with limited use of certain schemata
• A Logical Autobiography
• The deduction rule and linear and near-linear proof simulations
• scientific article; zbMATH DE number 1342249 (Why is no real title available?)
• A note on the complexity of propositional Hoare logic
• Proof Complexity of Non-classical Logics
• scientific article; zbMATH DE number 1860672 (Why is no real title available?)
• Exponential lower bounds for the tree-like Hajós calculus
• Interpolants, cut elimination and flow graphs for the propositional calculus

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4010371)