Proof-nets: the parallel syntax for proof theory
The paper is mainly concerned with the extension of proof-nets to additives, for which the best known solution is presented. It proposes two cut-elimination procedures, the lazy one being in linear time. The solution is shown to be compatible with quantifiers, and the structural rules of exponentials are also accommodated. Traditional proof-theory deals with cut-elimination ; these results are usually obtained by means of sequent calculi, with the consequence that 75% of a cutelimination proof is devoted to endless commutations of rules. It is hard to be happy with this, mainly because : I the structure of the proof is blurred by all these cases ; I whole forests have been destroyed in order to print the same routine lemmas ; I this is not extremely elegant. However old-fashioned proof-theory, which is concerned with the ritual question : “is-that-theory-consistent ?” never really cared. The situation changed when subtle algorithmic aspects of cut-elimination became prominent : typically the determinism of cut-elimination, its actual complexity, its implementation cannot be handled in terms of sequent calculus without paying a heavy price. Natural deduction could easily fix the main drawbacks of cutelimination, but this improvement was limited to the negative fragment of intuitionistic logic. The situation changed in 1986 with the invention of linear logic : proof-nets were introduced in [G86] as a new kind of syntax for linear logic, in order to