✦ LIBER ✦

Tractability of cut-free Gentzen type propositional calculus with permutation inference

✍ Scribed by Noriko H. Arai

Book ID: 104326262
Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 902 KB
Volume: 170
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(96)80704-3

No coin nor oath required. For personal study only.

✦ Synopsis

We present a new propositional calculus that has desirable natures with respect to both automatic reasoning and computational complexity: we introduce an inference rule, called permutation, into a cut-free Gentzen type propositional calculus. It allows us to obtain a system which (1) guarantees the subformula property and (2) has polynomial size proofs for hard combinatorial problems, such as pigeonhole principles. We also discuss the relative efficiency of our system. Frege systems polynomially prove the partial consistency of our system.

📜 SIMILAR VOLUMES

Tractability of Cut-free Gentzen-type pr

Tractability of Cut-free Gentzen-type propositional calculus with permutation inference II

✍ Noriko H. Arai 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 114 KB

In Arai (1996), we introduced a new inference rule called permutation to propositional calculus and showed that cut-free Gentzen system LK (GCNF) with permutation (1) satisÿes the feasible subformula property, and (2) proves pigeonhole principle and k-equipartition polynomially. In this paper, we su

A Cut-Free Gentzen Formulation of Basic

A Cut-Free Gentzen Formulation of Basic Propositional Calculus

✍ Kentaro Kikuchi; Katsumi Sasaki 📂 Article 📅 2003 🏛 Springer Netherlands 🌐 English ⚖ 97 KB

[Lecture Notes in Computer Science] Logi

[Lecture Notes in Computer Science] Logic Based Program Synthesis and Transformation Volume 2664 || A Cut-Free Sequent Calculus for Pure Type Systems Verifying the Structural Rules of Gentzen/Kleene

✍ Leuschel, Michael 📂 Article 📅 2003 🏛 Springer Berlin Heidelberg 🌐 English ⚖ 250 KB

The thoroughly refereed post-proceedings of the 12th International Workshop on Logic Based Program Synthesis and Transformation, LOPSTR 2002, held in Madrid, Spain in September 2002. The 15 revised full papers presented together with 7 abstracts were carefully selected during two rounds of reviewing