𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On meta complexity of propositional formulas and propositional proofs

✍ Scribed by Pavel Naumov

Publisher
Springer
Year
2008
Tongue
English
Weight
213 KB
Volume
47
Category
Article
ISSN
0933-5846

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Proof complexity of propositional defaul
Proof complexity of propositional default logic
✍ Olaf Beyersdorff; Arne Meier; Sebastian MΓΌller; Michael Thomas; Heribert Vollmer πŸ“‚ Article πŸ“… 2011 πŸ› Springer 🌐 English βš– 551 KB
On the computational content of intuitio
On the computational content of intuitionistic propositional proofs
✍ Samuel R Buss; Pavel PudlΓ‘k πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 115 KB

The paper proves reΓΏned feasibility properties for the disjunction property of intuitionistic propositional logic. We prove that it is possible to eliminate all cuts from an intuitionistic proof, propositional or ΓΏrst-order, without increasing the Horn closure of the proof. We obtain a polynomial ti