An answer to an open problem of Urquhart

DOI10.1016/S0304-3975(97)00140-0zbMATH Open0901.03038OpenAlexW2085900785MaRDI QIDQ1129262FDOQ1129262

Authors: Uwe Egly 

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00140-0

Recommendations

• scientific article; zbMATH DE number 65760
• The relative complexity of resolution and cut-free Gentzen systems
• Propositional consistency proofs
• Simulating non-prenex cuts in quantified propositional calculus

zbMATH Keywords

proof complexitysequent calculuspropositional logicGentzen calculuspolynomial simulationanalytic cut ruleresolution with limited extension

Mathematics Subject Classification ID

Classical propositional logic (03B05) Cut-elimination and normal-form theorems (03F05) Complexity of proofs (03F20)

Cites Work

• A structure-preserving clause form translation
• Title not available (Why is that?)
• The Complexity of Propositional Proofs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of Gentzen systems for propositional logic
• On different structure-preserving translations to normal form
• Title not available (Why is that?)

Cited In (1)

• Non-elementary speed-ups in proof length by different variants of classical analytic calculi

This page was built for publication: An answer to an open problem of Urquhart

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