An answer to an open problem of Urquhart

DOI10.1016/S0304-3975(97)00140-0MaRDI QIDQ1129262zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 48763 (Why is no real title available?)
• scientific article; zbMATH DE number 3583767 (Why is no real title available?)
• scientific article; zbMATH DE number 3333259 (Why is no real title available?)
• scientific article; zbMATH DE number 3420722 (Why is no real title available?)
• A structure-preserving clause form translation
• On different structure-preserving translations to normal form
• The Complexity of Propositional Proofs
• The complexity of Gentzen systems for propositional logic

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)