Proof net

In proof theory, proof nets are a geometrical method of representing proofs that eliminates two forms of bureaucracy that differentiates proofs: (A) irrelevant syntactical features of regular proof calculi such as the natural deduction calculus and the sequent calculus, and (B) the order of rules applied in a derivation. In this way, the formal properties of proof identity correspond more closely to the intuitively desirable properties. Proof nets were introduced by Jean-Yves Girard.

For instance, these two linear logic proofs are “morally” identical:

\vdash A, B, C, D
\vdash AB, C, D
\vdash AB, CD
\vdash A, B, C, D
\vdash A, B, CD
\vdash AB, CD

And their corresponding nets will be the same.

Correctness criteria

Several correctness criteria are known to check if a sequential proof structure (i.e. something which seems to be a proof net) is actually a concrete proof structure (i.e. something which encodes a valid derivation in linear logic). The first such criterion is the long-trip criterion[1] which was described by Jean-Yves Girard.

See also

References

  1. Girard, Jean-Yves. Linear logic, Theoretical Computer Science, Vol 50, no 1, pp. 1–102, 1987

Sources

This article is issued from Wikipedia - version of the 4/17/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.