کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4662207 | 1633480 | 2007 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Extension without cut
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In proof theory one distinguishes sequent proofs with cut and cut-free sequent proofs, while for proof complexity one distinguishes Frege systems and extended Frege systems. In this paper we show how deep inference can provide a uniform treatment for both classifications, such that we can define cut-free systems with extension, which is neither possible with Frege systems, nor with the sequent calculus. We show that the propositional pigeonhole principle admits polynomial-size proofs in a cut-free system with extension. We also define cut-free systems with substitution and show that the cut-free system with extension p-simulates the cut-free system with substitution.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 163, Issue 12, December 2012, Pages 1995-2007
Journal: Annals of Pure and Applied Logic - Volume 163, Issue 12, December 2012, Pages 1995-2007