Can I read Proof-graphs for Minimal Implicational Logic on EtoBox?

Proof-graphs for Minimal Implicational Logic by Quispe-Cruz, Marcela; Haeusler, Edward Hermann; Gordeev, Lew is a scholarly article available to read on EtoBox.

What is Proof-graphs for Minimal Implicational Logic about?

It is well-known that the size of propositional classical proofs can be huge. Proof theoretical studies discovered exponential gaps between normal or cut free proofs and their respective non-normal proofs. The aim of this work is to study how to reduce the weight of propositional deductions. We present the formalism of proof-graphs for purely implicational logic, which are graphs of a specific shape that are intended to capture the logical structure of a deduction. The advantage of this formalism is that formulas can be shared in the reduced proof. In the present paper we give a precise definition of proof-graphs for the minimal implicational logic, together with a normalization procedure for these proof-graphs. In contrast to standard tree-like formalisms, our normalization does not increase the number of nodes, when applied to the corresponding minimal proof-graph representations.

Author

Quispe-Cruz, Marcela; Haeusler, Edward Hermann; Gordeev, Lew

Published

2014

Language

EN