Mathematics – Logic
Scientific paper
2008-01-16
Mathematics
Logic
24 pages
Scientific paper
This paper presents proof nets for multiplicative-additive linear logic (MALL), called conflict nets. They are efficient, since both correctness and translation from a proof are p-time (polynomial time), and abstract, since they are invariant under transposing adjacent &-rules. A conflict net on a sequent is concise: axiom links with a conflict relation. Conflict nets are a variant of (and were inspired by) combinatorial proofs introduced recently for classical logic: each can be viewed as a maximal map (homomorphism) of contractible coherence spaces (P_4-free graphs, or cographs), from axioms to sequent. The paper presents new results for other proof nets: (1) correctness and cut elimination for slice nets (Hughes / van Glabbeek 2003) are p-time, and (2) the cut elimination proposed for monomial nets (Girard 1996) does not work. The subtleties which break monomial net cut elimination also apply to conflict nets: as with monomial nets, existence of a confluent cut elimination remains an open question.
No associations
LandOfFree
Abstract p-time proof nets for MALL: Conflict nets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Abstract p-time proof nets for MALL: Conflict nets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Abstract p-time proof nets for MALL: Conflict nets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-159516