betaFeedback

WorksComputer Science

Canonical Proof Nets for Intuitionistic Multiplicative Linear Logic

Abstract

We study the problem of finding canonical representations of proofs in the multiplicative fragment of intuitionistic linear logic with units. We show that, contrary to the classical case, it is possible to define a notion of proof nets for this fragment which is provided with a polynomial-time sequentialization procedure and is both canonical and efficient. In particular, we show that sequent calculus derivations differing only by a permutation of independent rule applications are translated to the same proof net, and that the translations between sequent calculus and proof nets are inverse to each other.

Introduction

Proof nets are a graph-based syntax for proofs introduced by Girard [11] in the context of linear logic [10]. One of its motivations was to provide an analogous of natural deduction for linear logic, that is, a syntax for proofs that would be free of the bureaucratic aspects of the sequent calculus, such as the order of independent rule applications. The central idea of proof nets is to replace the sequent calculus rules with graph-based constructs, called gates, connecting active and principal formulas of rules, and to represent proofs as graphs generated by these gates. The benefit in replacing sequent calculus rules with gates is the fact that they make it possible to track dependencies between rule applications, while abstracting away from the ordering of rules that operate on disjoint sets of active and principal formulas.

ax⊢a⊥,aax⊢b⊥,b⊢a⊥,a⊗b⊥,b ⊗ax⊢c⊥,c⊢a⊥,a⊗b⊥,b⊗c⊥,c ⊗∼ax⊢a⊥,aax⊢b⊥,bax⊢c⊥,c⊢b⊥,b⊗c⊥,c ⊗⊢a⊥,a⊗b⊥,b⊗c⊥,c ⊗(1)\frac{\frac{\frac{\mathrm{ax}}{\vdash a^{\bot},a}\quad\frac{\mathrm{ax}}{\vdash b^{\bot},b}}{\vdash a^{\bot},a\otimes b^{\bot},b}\ \otimes\quad\frac{\mathrm{ax}}{\vdash c^{\bot},c}}{\vdash a^{\bot},a\otimes b^{\bot},b\otimes c^{\bot},c}\ \otimes \quad\sim\quad \frac{\frac{\mathrm{ax}}{\vdash a^{\bot},a}\quad\frac{\frac{\mathrm{ax}}{\vdash b^{\bot},b}\quad\frac{\mathrm{ax}}{\vdash c^{\bot},c}}{\vdash b^{\bot},b\otimes c^{\bot},c}\ \otimes}{\vdash a^{\bot},a\otimes b^{\bot},b\otimes c^{\bot},c}\ \otimes \tag*{(1)}
axaxax⊢a⊥a⊗b⊥b⊗c⊥c\begin{gathered} \mathrm{ax}\quad\mathrm{ax}\quad\mathrm{ax}\\ \vdash a^{\bot}\quad a\otimes b^{\bot}\quad b\otimes c^{\bot}\quad c \end{gathered}

In the multiplicative fragment of linear logic (MLL), the tree-like structure of formulas already captures all the dependencies between rules, and thus only missing information to fully identify a proof is the pairing of dual formulas corresponding to the logical axioms used in the derivation.

a⊥a⊗b⊥b⊗c⊥c(2)a^\perp\quad a \otimes b^\perp\quad b \otimes c^\perp\quad c \tag*{(2)}

This yields canonical representations of proofs: sequent calculus derivations that differ only in the order of independent rule applications are represented by the same proof net.1

However, trade-offs are inevitable. While proof nets eliminate the bureaucracy of sequent calculus syntax, they introduce the need for correctness criteria to distinguish proof structures (i.e., graphs freely constructed using gates) from proof nets (i.e., graphs encoding correct proofs).

Correct Proof Nets and Incorrect Proof Structures, showing axiom and tensor gates

Figure 1.3.

Moreover, although the basic idea of proof nets works elegantly for the multiplicative fragment of linear logic, it does not generalize well in the presence of rules with a structural character, such as weakening and contraction, or even units and additive connectives. The root of this issue lies in the fact that the rules-as-gates approach fail to capture non-local dependencies. For example, the rule for the negative multiplicative unit ⊥\bot (see Figure 3) can only be applied to a non-empty context, while the rule for additive conjunction requires that both premises share the same context.2

The problem of multiplicative units. The design of a syntax for proof nets that allows for canonical representations of proofs in MLL with units admitting both a polynomial-time correctness criterion a polynomial-time proof translation has been a long-standing open problem. A key idea to recover a way to easily check the correctness of an application of the ⊥\bot-rule is to include additional edges connecting a ⊥\bot-gate to another gate in the proof net, called jumps, to represent the connection between the ⊥\bot-gate and the context in which it is applied.3 This makes it possible to ensure that the ⊥\bot-gate corresponds to a valid application of the ⊥\bot-rule, even in the absence of syntactic structure indicating the entire surrounding context. However, while jumps guarantee polynomial-time proof translation and correctness criterion, the presence of jumps breaks canonicity: two derivations that should be considered equivalent modulo rule permutations may be represented by different proof nets solely because of jumps, as shown in Figure 1.

Three distinct derivations and their corresponding proof nets

Figure 1. Three distinct derivations equivalent derivations and their corresponding proof nets. The one in the middle is the canonical proof net providing the canonical representative of equivalence class.

The work of Heijltjes and Houston [12] ruled out the existence of a satisfactory solution to this problem capable of balancing canonicity with efficiency of both proof translation and correctness criterion4 Their result follows from showing that the reconfiguration problem [21] in constraint logic [7] can be reduced to the problem of proof equivalence in the fragment of MLL containing only units dealing with jumps rewiring.5 Thus, if canonical proof nets with a polynomial-time proof translation existed, we could translate two derivations into proof nets and test their equivalence in polynomial time, implying that the complexity classes PTIME and PSPACE should coincide. Of course, one could ‘cheat’ and define a canonical proof net by defining it as the set of all possible proof nets with jumps corresponding to a given derivation, but this would lead to an exponential blow-up in the size of the proof net, as the one encountered in monomial and Slice nets for MALL [18, 17].

Therefore, under the assumption PTIME ≠\ne PSPACE, we have the following consequence:

There cannot be canonical proof nets for MLL (with units) with PTIME proof translation and PTIME correctness criterion.

At the time of writing, it is still an open question whether the multiplicative fragment of intuitionistic linear logic (IMLL) admits proof nets with a polynomial-time correctness criterion and polynomial-time proof translation capturing the equivalence induced by independent rule permutations. If one considers the negative results for MLL with units, one could be tempted to conclude that the same result should hold for IMLL, but this is not the case. However, Lamarche’s correctness criterion for essential nets [23] restricted to IMLL, while similar to Danos-Regnier switching criterion for MLL [6], is simpler and more efficient, leaving room for a possible solution to the problem of canonicity for IMLL.

Contribution. In this paper, we show that the problem of canonicity for IMLL admits a quite simple solution, and that the problem of canonicity for MLL does not affect IMLL. For this, we look at Lamarche’s proof nets for IMLL [23], and we show that there is a simple natural way to exploit the same mechanism used to check correctness to define a canonical way to assign jumps to negative units.

The idea is to observe that the correctness criterion for proof nets for IMLL naturally defines paths oriented towards the consequent of the sequent, and that we can use these paths to define a canonical way to assign jumps to negative units. For example, while the three derivations in Figure 1 are all equivalent, their corresponding proof nets differ in the way jumps are assigned to the negative unit ∘\circ. However, the proof net in the middle is the only one which is canonical, because the jumps cannot be pushed forward along the paths defined by the correctness criterion.

The properties on the resulting proof nets are summarized in Figure 2. Interestingly, we can show a surprising result which does not hold for MLL: it is possible to define a polynomial-time correctness criterion and sequentialization procedure for proof nets without jumps which is sound and complete for IMLL (with units). Similar attempt to define proof nets for IMLL without jumps have been proposed in the literature, but they all fail to be complete.

Figure 2. Relations between different properties of proof structures for IMLL with units. Here sequentializable means there is a polynomial time procedure to construct a derivation in the sequent calculus, total means that each negative unit has an associated jump, and maximal means that the jumps are assigned ‘as closer to the output as possible’ to the consequent of the sequent with respect to the order induced by the correctness criterion.

Structure of the paper. In § 2 we recall the definition of the sequent calculus for IMLL and its proof nets, and we fix the notation for formulas, sequents, and formula trees we use in the paper. In § 3 we recall the definition of proof nets for IMLL and we recall Lamarche’s correctness criterion for pure multiplicative essential nets. In § 4 we define a canonical way to rewire jumps from negative units to positive formulas, and we show that the resulting proof nets are canonical, and we define a cut-elimination procedure for canonical proof nets. In § 5 we discuss a correctness criterion for proof nets without jumps enforcing a stronger quotient on proofs. We conclude in § 6 with some remarks and future directions.

Background

In this section we briefly fix the notation and recall the definition of the sequent calculus for IMLL and its proof nets, which we will use in the rest of the paper.

Intuitionistic Multiplicative Linear Logic

Intuitionistic Multiplicative Linear Logic. Formulas are generated from a countable set of propositional variables (or atoms) A={a,b,…}A = \{a,b,\ldots\} and the unit (1)(1) using the logic operators linear implication (⊸)(\multimap), and tensor (⊗)(\otimes) as follows:

A,B:=a∣1∣A⊸B∣A⊗B(3)A,B := a \mid1 \mid A \multimap B \mid A \otimes B \tag*{(3)}

A context Γ=A1,…,An\Gamma= A_1,\ldots,A_n is a comma-separated list of formulas sequence which we interpret as a multiset, that is, the order of formulas in a context does not matter, and formulas can occur multiple times in a context. A sequent Γ⊢A\Gamma\vdash A comprises a context Γ\Gamma (the antecedent) and a formula AA (the consequent).

In this paper, we identify formulas with their parse trees, thus occurrences of atoms, units, and connectives in a formula are identified with the unique corresponding node of the parse tree. For example, we identify the formula

(((p⊗1)⊸p)⊸(q⊗1))⊗(1⊸1)⊸((p⊸p)⊗q)(4)(((p \otimes1) \multimap p) \multimap(q \otimes1)) \otimes(1 \multimap1) \multimap((p \multimap p) \otimes q) \tag*{(4)}

with its parse tree, which is depicted as follows:

p1pq111ppq⊗⊗⊸⊸⊸⊗⊸(5)\begin{array}{c} p\quad1\quad p\quad q\quad1\quad1\quad1\quad p\quad p\quad q\\ \otimes\quad\otimes\quad\multimap\quad\multimap\\ \multimap\quad\otimes\quad\multimap \tag*{(5)} \end{array}

A node of a sequent is any node of the parse tree of a formula occurring in a sequent, that is, any occurrence of an atom, unit, or connective in a formula occurring in a sequent. Two sub-formulas in a sequent are disjoint if they do not share any node.

Definition 2.1. The implication depth of a sequent node is the number of times it occurs in the left argument (sub)formula of a ⊸\multimap or ⊢\vdash. For example, each node in the following sequent has its implication depth annotated over it:

((p⊗1)⊸p)⊸(q⊗1), 1⊸1⊢(p⊸p)⊗q((p⊗1)⊸p)⊸(q⊗1), 1⊸1⊢(p⊸p)⊗q3  3  3  2  2  1  1  1  1  2  1  1  1  0  0  0  0\begin{aligned} &((p \otimes1) \multimap p) \multimap(q \otimes1),\ 1 \multimap1 \vdash(p \multimap p) \otimes q\\ &\phantom{((p \otimes1) \multimap p) \multimap(q \otimes1),\ 1 \multimap1 \vdash(p \multimap p) \otimes q}\quad3\ \ 3\ \ 3\ \ 2\ \ 2\ \ 1\ \ 1\ \ 1\ \ 1\ \ 2\ \ 1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0 \end{aligned}

We say that a node is positive if its implication depth is even, and negative if its implication depth is odd.

Notation 2.2. In the following, we may annotate nodes with negative variance by decorating them with a overline. For example, we may write the sequent above as follows:

((p‾⊗1‾)⊸p)⊸(q⊗1‾)‾, 1‾⊸1‾⊢(p‾⊸p)⊗q((\overline{p} \otimes\overline{1}) \multimap p) \multimap\overline{(q \otimes\overline{1})},\ \overline{1} \multimap\overline{1} \vdash(\overline{p} \multimap p) \otimes q

Similarly, if a sub-formula has its root node with negative variance, we may write it with a overline, for example:

((p⊗1)⊸p)‾⊸(q⊗1)‾, 1⊸1‾⊢(p⊸p)‾⊗q.\overline{((p \otimes1) \multimap p)} \multimap\overline{(q \otimes1)},\ \overline{1 \multimap1} \vdash\overline{(p \multimap p)} \otimes q .
a⊢a axΓ⊢AΔ⊢BΓ,Δ⊢A⊗B ⊗Γ⊢AB,Δ⊢CΓ,A⊸B,Δ⊢C ⊸Γ⊢CC,Δ⊢AΓ,Δ⊢A cut⊢1 1Γ⊢AΓ,1⊢A 1‾Γ,A,B⊢CΓ,A⊗B⊢C ⊗‾Γ,A⊢BΓ⊢A⊸B ⊸‾A⊢A AX\begin{aligned} &\frac{}{a \vdash a}\ \mathrm{ax} &&\frac{\Gamma\vdash A \quad\Delta\vdash B}{\Gamma,\Delta\vdash A \otimes B}\ \otimes &&\frac{\Gamma\vdash A \quad B,\Delta\vdash C}{\Gamma,A \multimap B,\Delta\vdash C}\ \multimap &&\frac{\Gamma\vdash C \quad C,\Delta\vdash A}{\Gamma,\Delta\vdash A}\ \mathrm{cut}\\ &\frac{}{\vdash1}\ 1 &&\frac{\Gamma\vdash A}{\Gamma,1 \vdash A}\ \overline{1} &&\frac{\Gamma,A,B \vdash C}{\Gamma,A \otimes B \vdash C}\ \overline{\otimes} &&\frac{\Gamma,A \vdash B}{\Gamma\vdash A \multimap B}\ \overline{\multimap}\\ &&&&&&\frac{}{A \vdash A}\ \mathrm{AX} \end{aligned}

fig:3: Sequent rules for IMLL, and the rules for the generalized AX and cut.

In fig:3 recall the definition of the sequent calculus for intuitionistic multiplicative linear logic (IMLL), and we recall the admissible rules for the generalized axiom and cut rules, which we will use in the rest of the paper. We say that a formula is active (resp. principal) for a rule if it occurs in a premise (resp. in the conclusion) of the rule but not in the conclusion (resp. in none of the premises).

Remark 2.3. Notice that for the rules for the implication and tensor connectives we adopt names which reflect whether the main connective of the active formula negative or positive, that is, if it occurs in the antecedent or in the consequent of the sequent respectively.

A derivation is a tree of sequents such that each node of the tree is the conclusion of a rule instance whose premises are the children of the node. In particular, its leaves are conclusion of the rules ax and 1.

Theorem 2.4. In IMLL, the following hold:

  • the general axiom rule AX is derivable;

  • the rule cut is admissible.

Proof. To prove the derivability of AX, we proceed by induction on AA. If AA is an atom, then the derivation is just an instance of ax. If AA is 11, then the derivation is an instance of 1‾\overline{1} followed (bottom-up) by an instance of 11. If AA is B⊸CB \multimap C (resp. B⊗CB \otimes C), then the derivation is an instance of ⊸\multimap (resp. ⊗\otimes) followed (bottom-up) by a ⊸‾\overline{\multimap} (resp. ⊗‾\overline{\otimes}) with premises the sequents B⊢BB \vdash B and C⊢CC \vdash C, which are both derivable by induction hypothesis.

To prove the admissibility of cut, we use the cut-elimination steps recalled in Figure 4 to push cut-rules upwards in the derivation until they reach the axioms, where they can be eliminated. Termination of the cut-elimination procedure follows from the fact that each principal cut-elimination step strictly decreases the size of the cut formula, while each commutative cut-elimination step strictly decreases the maximum length of the branches above the cut-rule in the derivation.

Cut-elimination steps for IMLL

Figure 4. Cut-elimination steps for IMLL.

Graphs

We recall standard definitions for graphs and formula trees to fix the notation we use in the paper. Then, we define a natural notion of variance for nodes of the forest encoding the formulas in a sequent which plays a crucial role in the definition of our proof nets for IMLL with units.

A (direct) graph defined as triples of the form G=⟨VG,→G⟩\mathcal{G}=\langle V_{\mathcal{G}},\mathord{\to_{\mathcal{G}}}\rangle made of a (finite) set of vertices VGV_{\mathcal{G}}, and a set of edges →G\mathord{\to_{\mathcal{G}}} whose elements are pairs of vertices, written vwvw or v→wv \to w. In an edge v→wv \to w, we call vv its source and ww its target. Two vertices are adjacent if there is an edge connecting them. The size of a graph is the sum of the number of its vertices and edges.

A path in a graph G\mathcal{G} form a vertex uu to a vertex ww of length nn is a sequence of vertices v0⋯vnv_0 \cdots v_n such that u=v0u=v_0 and w=vnw=v_n, and such that vi→vi+1v_i \to v_{i+1} for all i∈{1,…,n−1}i \in\{1,\ldots,n-1\}. A

cycle in G\mathcal{G} is a path of positive length from a vertex vv to itself. A graph G\mathcal{G} is a directed acyclic graph (or dag) if it contains no cycles. A tree is a dag with a single vertex rr (called its root) such that there is a path from any other vertex of the graph to rr. A leaf is a vertex which is not the target of any edge.

Notation 2.5. We depict the edges of a graph G\mathcal{G} by arrows between them. For example, the graph G=⟨{a,b,c,d},{ab,bd,cd}⟩\mathcal{G} = \langle\{a,b,c,d\}, \{ab,bd,cd\}\rangle can be represented as a⟶bc⇉da \longrightarrow b \quad c \rightrightarrows d. In some cases, we assume the vertices have label naturally defined, in which case we represent them by their label.

Proof Nets

In this section we reformulate Lamarche’s syntax for essential nets [23] for IMLL with units, and we show how to use them to define a canonical way to assign jumps to negative units, which yields a canonical representation of proofs in IMLL.6

Definition 3.1. A link on a sequent Γ⊢A\Gamma\vdash A is a pair of nodes λ=⟨v,w⟩\lambda= \langle v,w\rangle such that vv is a negative leaf. It is an axiom link if vv and ww are occurrences of the same atom, and a jump if vv is an occurrence of 11.

A linking Λ\Lambda on a sequent Γ⊢A\Gamma\vdash A is a function associating a link to each negative leaf of Γ⊢A\Gamma\vdash A. It is axiomatic if the restriction of Λ\Lambda to the negative atoms forms a bijection between non-unit leaves.

Notation 3.2. We represent links by edges connecting the corresponding nodes in the sequent. In particular, we use squared edges to represent axiom links, and curved edges to represent jumps, as shown in the following example.

Example 3.3. Consider the sequent containing the formula Equation (4) in the consequent, and no formula in the antecedent, and the following linking Λ\Lambda on it.

(((p⊗1)⊸p)⊸(q⊗1))⊗(1⊸1)⊸((p⊸p)⊗q)(6)\left(\left((p \otimes1) \multimap p\right) \multimap(q \otimes1)\right) \otimes(1 \multimap1) \multimap\left((p \multimap p) \otimes q\right) \tag*{(6)}

In order to write it down as a set of pairs of nodes, we should annotate atoms and units to distinguish their occurrences (i.e., distinguish their nodes). For example, if we annotate the atoms, some units and connectives as follows

(((p1⊗11)⊸p2)⊸(q1⊗13))⊗(1⊸15)⊸((p3⊸p4)⊗0q2)\left(\left((p_{1} \otimes1_{1}) \multimap p_{2}\right) \multimap(q_{1} \otimes1_{3})\right) \otimes(1 \multimap1_{5}) \multimap\left((p_{3} \multimap p_{4}) \otimes_{0} q_{2}\right)

then Λ\Lambda can be written as the following set of pairs of nodes

Λ={⟨p1,p2⟩,⟨p3,p4⟩,⟨q1,q2⟩,⟨11,p2⟩,⟨13,⊗0⟩,⟨15,⊗0⟩}\Lambda= \{\langle p_{1},p_{2}\rangle, \langle p_{3},p_{4}\rangle, \langle q_{1},q_{2}\rangle, \langle1_{1},p_{2}\rangle, \langle1_{3},\otimes_{0}\rangle, \langle1_{5},\otimes_{0}\rangle\}

We define proof nets as linkings obtained by translating derivations in IMLL or, equivalently, as linkings constructed by the rules in Figure 5, mimicking the rules of the sequent calculus for IMLL.

Figure 5. Translation of IMLL derivations into proof nets, with ρ∈{⊸,⊗}\rho\in\{\multimap,\otimes\} and τ∈{⊸,⊗}\tau\in\{\multimap,\otimes\}. Note that linkings are defined over the nodes of the sequents, which are disjoint for disjoint sequents, thus the union is always disjoint.

Definition 3.4. A pre-net is a pair Λ::Γ⊢A=⟨Γ⊢A,Λ⟩\Lambda:: \Gamma\vdash A = \langle\Gamma\vdash A,\Lambda\rangle made of a sequent Γ⊢A\Gamma\vdash A and a linking Λ\Lambda on Γ⊢A\Gamma\vdash A.

A proof net for a sequent Γ⊢A\Gamma\vdash A is the pre-net Λ::Γ⊢A\Lambda:: \Gamma\vdash A with linking Λ\Lambda induced by a derivation D\mathcal{D} in IMLL with conclusion Γ⊢A\Gamma\vdash A as follows:

  • each ax with conclusion aˉ⊢a\bar{a} \vdash a induces an axiomatic link aˉ⊢a\bar{a} \vdash a in λ\lambda;

  • each 1ˉ\bar{1}-rule with conclusion 1ˉ,Γ⊢A\bar{1},\Gamma\vdash A induces a jump link 1ˉ⊢A\bar{1} \vdash A in λ\lambda.

Equivalently, a proof net is a pre-net generated by rules in Figure 5.

Example 3.5. Below, a derivation in IMLL with the same conclusion is shown, together with its translation into a proof net, where we connect with an edge each pair of nodes in a same link (see Equation (3.3)).

We end this section by recalling the correctness criterion for Lamarche’s proof nets for full intuitionistic linear logic in the case of IMLL. We slightly change the original definition of test in [23] by inverting the direction of the edges to ensure that linkings can always be considered as functions. In fact, using the opposite direction a same vertex may be the source of more than one edge, as in the case of the (unique) proof net of the sequent 1,1⊢11,1 \vdash1.

Definition 3.6. The test of a pre-net Λ::Γ⊢A\Lambda:: \Gamma\vdash A is the directed graph T(Λ::Γ⊢A)T(\Lambda:: \Gamma\vdash A) with vertices the nodes of Γ⊢A\Gamma\vdash A, and edges defined either by the links in Λ\Lambda (marked as →\to) as follows:

Axiom link and jump

Figure 7.

or by the sub-formula relations (marked as →\to) as follows:

\begin{array}{c@{\qquad}c} \text{tensor} & \text{implication} \\ P \otimes Q \qquad N \otimes M & N \multimap P \qquad P \multimap N \\ \text{positive}\qquad\text{negative} & \text{positive}\qquad\text{negative} \tag*{(7)} \end{array}

where source and target of the edges are the root nodes of the corresponding sub-formulas.

Remark 3.7. If Γ⊢A\Gamma\vdash A is a sequent, and NN is a negative sub-formula of Γ⊢A\Gamma\vdash A, then there are always paths from NN to any negative leaf of the sub-tree of the parse tree of NN.

The correctness criterion for proof nets is defined in terms of the paths in the test of a pre-net, as follows.

Definition 3.8. Let Λ::Γ⊢A\Lambda:: \Gamma\vdash A be a pre-net. It is correct if it satisfies the following conditions:

(1) its test is acyclic.

(2) B→ ⁣→AB \mathrel{\to\!\to} A for any sub-formula BB of Γ⊢A\Gamma\vdash A.

(3) if L⊸RL \multimap R is a (positive) sub-formula in Γ⊢A\Gamma\vdash A, then any maximal path in the test starting from LL contains RR.

where by B→ ⁣→CB \mathrel{\to\!\to} C we denote the existence of a path from (the root node of) BB to (the root node of) CC in the test T(Λ::Γ⊢A)T(\Lambda:: \Gamma\vdash A).

Example 3.9. The test of the linking in Equation (6) is the following graph.

(((p‾⊗1)⊸p)⊸(q‾⊗1))⊗(1⊸1)⊸((p‾⊸p)⊗q)(8)\bigl(((\overline{p}\otimes1)\multimap p)\multimap(\overline{q}\otimes1)\bigr)\otimes(1\multimap1)\multimap\bigl((\overline{p}\multimap p)\otimes q\bigr) \tag*{(8)}

Remark 3.10. The edges defined by the sub-formula relation in Equation (7) can be seen as directing the connections in the parse tree of the sequent downward (resp. upward) if touching two positive nodes (resp. at least one negative node), and removing the edge from the left child of a positive implication to its parent.

For example, the test in Equation (5) can be seen as the directed graph shown below, where the dotted edges are shown for uniformity (to keep track of the sub-formula relation), but they are not part of the test.

p‾1pq‾111p‾pq⊗⊗⊸⊸⊸⊗⊗(9)\begin{gathered} \overline{p}\quad1\quad p\qquad\overline{q}\quad1\quad1\quad1\qquad\overline{p}\quad p\quad q\\ \otimes\qquad\qquad\qquad\otimes\qquad\multimap\qquad\qquad\multimap\\ \multimap\qquad\qquad\otimes\qquad\qquad\qquad\otimes \tag*{(9)} \end{gathered}

Theorem 3.11. A pre-net Λ::Γ⊢A\Lambda:: \Gamma\vdash A is a proof net if and only if it is correct.

Sketch of proof. We recall the main ideas of the proof from of the correctness criterion for essential nets from [23], which can be reformulated straightforwardly in our setting. The right-to-left direction is proved by induction on the structure of a derivation D\mathcal{D} of the sequent Γ⊢A\Gamma\vdash A, and by checking that the linking ΛD\Lambda_{\mathcal{D}} defined by the translation of D\mathcal{D} is correct.

The left-to-right direction is proved by showing that if Λ::Γ⊢A\Lambda:: \Gamma\vdash A is a correct pre-net, then we can sequentialize it, that is, we can construct a derivation D\mathcal{D} of Γ⊢A\Gamma\vdash A such that ΛD=Λ\Lambda_{\mathcal{D}} = \Lambda.

  • If Γ⊢A\Gamma\vdash A is of the form ⊢1\vdash1 or a⊢aa \vdash a, then we can easily construct such derivation, which would be made of a single rule application of 11 or ax respectively.

  • Similarly, if Γ\Gamma contains a unit 11 or a ⊗\otimes-formulas, or if AA is a ⊸\multimap-formula, then we can apply the corresponding rule to construct a derivation D\mathcal{D} of Γ⊢A\Gamma\vdash A such that ΛD=Λ\Lambda_{\mathcal{D}} = \Lambda, and we can apply the induction hypothesis to the resulting sub-pre-net. Notice that the correctness condition 3 ensures that if AA is a ⊸\multimap-formula, then removing the main connective of AA will preserve the existence of paths from any sub-formula to the root of the consequent, which is required to apply the induction hypothesis.

  • If Γ⊢A\Gamma\vdash A is not of the above forms, then either A=A1⊗A2A = A_1 \otimes A_2 or a formula A1⊸A2A_1 \multimap A_2 in Γ\Gamma is splitting, that is, such that removing the main connective of the formula the test of the pre-net becomes disconnected into two components, each satisfying the correctness criterion. In this case, we apply the corresponding two-premises rule to the main connective of the splitting formula, and conclude by applying the induction hypothesis to the resulting sub-pre-nets.

To prove the existence of a splitting formula, it suffices to observe that the paths in the test form a partial ordering on the sub-formulas of Γ⊢A\Gamma\vdash A (by conditions 2 and 3), and that if none of the formulas in Γ⊢A\Gamma\vdash A is splitting, then there should be either a cycle, contradicting the correctness condition 1.

Canonicity

In this section, we first recall the definition of proof equivalence in IMLL induced by rule permutations, showing that the proof nets defined in the previous section are not canonical with respect to this equivalence. Then, we introduce the notion of maximality for a linking, allowing us to define a canonical way to assign jumps, which yields a canonical representation of proofs in IMLL. For our canonical proof nets, we show a proof translation from sequent calculus derivations, and we explain how to define cut-elimination steps on them, which are strongly normalizing and confluent.

Proof equivalence in IMLL

The standard way to define proof equivalence in a sequent calculus is by considering derivations to be equivalent modulo the permutations of independent inference rules, where two inference rules are independent if they operate on different formulas of the sequents, that is, if their active and principal formulas are different and not in a sub-formula relation.

In Figure 6 we list the rule permutations defining the proof equivalence ∼\sim in IMLL {cut}\{\mathrm{cut}\} defined by the independent rule permutations. Note that for the unary-vs-binary right permutations the case ⊗\otimes-vs-⊸\multimap is ruled out since both apply to the consequent of their sequent, and thus they cannot be independent.

An IMLL derivation and its translation into a proof net

Figure 6.

Independent rule permutations in IMLL ∪ {cut}

Figure 6 (PDF p. 12). Independent rule permutations in IMLL ∪\cup {cut}.

It is immediate to show that there are equivalent derivations in IMLL whose translations into proof nets are not the same. In fact, the permutations binary left-vs-unary or unary-vs-binary right with the unary rule being a 1ˉ\bar{1} can change the jump links, since they change the position of the jump associated to the unit introduced by the 1ˉ\bar{1}-rule (see Figure 5). For example, see Figure 1.

Proposition 4.1. Let D1\mathcal{D}_1 and D2\mathcal{D}_2 be two derivations in IMLL. If D1∼D2\mathcal{D}_1 \sim\mathcal{D}_2, the set of axiom links in ΛD1\Lambda_{\mathcal{D}_1} and ΛD2\Lambda_{\mathcal{D}_2} are the same, but the set of jump links in ΛD1\Lambda_{\mathcal{D}_1} and ΛD2\Lambda_{\mathcal{D}_2} may be different.

At the same time, it is not difficult to show that given two derivations D1\mathcal{D}_1 and D2\mathcal{D}_2 obtained by sequentializing the same proof net, then D1∼D2\mathcal{D}_1 \sim\mathcal{D}_2.

Lemma 4.2. Let D1\mathcal{D}_1 and D2\mathcal{D}_2 be two derivations in IMLL. If ⟦D1⟧=⟦D2⟧\llbracket\mathcal{D}_1 \rrbracket= \llbracket\mathcal{D}_2 \rrbracket, then D1∼D2\mathcal{D}_1 \sim\mathcal{D}_2.

Recovering Canonicity

To recover canonicity, we use the fact that the test of a linking is a directed acyclic graph where every node n\mathfrak{n} admits a path to the root r\mathfrak{r} of the consequent to define a partial ordering of linkings. Using this partial ordering, we can define a notion of extension of a linking, and a notion of maximal linking (i.e., a linking that cannot be extended). By showing that the maximal extension of a linking is unique, and that the process of extending a linking is invariant with respect to the proof equivalence ∼\sim, we can conclude that the maximal extension of the translation of a derivation is a canonical representation of the equivalence class of the derivation, and thus we obtain a way to assign jumps to negative units in a canonical way, which yields a canonical representation of proofs in IMLL.

Local transformation of the jumps of a proof net under simple extension

Figure 7 (PDF p. 13). The local transformation of the jumps of a proof net when performing a simple extension. The simple extensions on a ⊗\otimes always induce a critical pair in the rewriting.

Definition 4.3. Let Λ\Lambda and Λ′\Lambda' be two linkings on the same sequent Γ⊢A\Gamma\vdash A. We say that Λ′\Lambda' is a simple extension of Λ\Lambda if Λ′\Lambda' is obtained by shifting the target of a jump in Λ\Lambda along an edge in the test of Λ\Lambda, that is, if Λ′=(Λ∖{⟨v,w⟩})∪{⟨v,w′⟩}\Lambda' = (\Lambda\setminus\{\langle v,w\rangle\}) \cup\{\langle v,w'\rangle\} for some ⟨v,w⟩∈Λ\langle v,w\rangle\in\Lambda and w′w' such that there is an edge ww′ww' in T(Λ)T(\Lambda). See Figure 7.

A linking Λ\Lambda is maximal if no simple extension of Λ\Lambda is correct. A proof net Λ::Γ⊢A\Lambda:: \Gamma\vdash A is canonical if its linking is maximal.

Remark 4.4. If Λ\Lambda is a linking on Γ⊢A\Gamma\vdash A and there is a jump in Λ\Lambda with target a negative node ww of Γ⊢A\Gamma\vdash A, then Λ\Lambda is not maximal. This is because either

  • ww is a leaf of the parse tree of Γ⊢A\Gamma\vdash A, in which case it must belong to an axiom link, and we can shift the jump to the other node of the axiom link;

  • or ww is not a leaf of the parse tree of Γ⊢A\Gamma\vdash A, in which case it must be either a ⊗\otimes-node or a ⊸\multimap-node, and we can always shift the jump to one of its children without violating the correctness Condition 3.

Example 4.5. The following proof net (where me marked the additional edges of its test) is not maximal because the jump could be extended along the highlighted edge.

since it can be extended by (repeatedly) shifting the jump as follows:

1‾⊗(1‾⊸a‾)⊸a→ext1‾⊗(1‾⊸a‾)⊸a\overline{1}\otimes\left(\overline{1}\multimap\overline{a}\right)\multimap a \xrightarrow{\mathrm{ext}} \overline{1}\otimes\left(\overline{1}\multimap\overline{a}\right)\multimap a
1‾⊗(1‾⊸a‾)⊸a→ext1‾⊗(1‾⊸a‾)⊸a\overline{1}\otimes\left(\overline{1}\multimap\overline{a}\right)\multimap a \xrightarrow{\mathrm{ext}} \overline{1}\otimes\left(\overline{1}\multimap\overline{a}\right)\multimap a
1‾⊗(1‾⊸a‾)⊸a→ext1‾⊗(1‾⊸a‾)⊸a\overline{1}\otimes\left(\overline{1}\multimap\overline{a}\right)\multimap a \xrightarrow{\mathrm{ext}} \overline{1}\otimes\left(\overline{1}\multimap\overline{a}\right)\multimap a

Notice that the last linking is maximal, since a further extension would violate the correctness condition 3. In fact, the only possible extension of the last linking would be the following linking obtained by shifting the target of the jump to be the ⊸\multimap-node, as shown below.

1‾⊗(1‾⊸a‾)⊸a\overline{1}\otimes\left(\overline{1}\multimap\overline{a}\right)\multimap a

However, this would result in having a path in the test from the ⊗\otimes-node (i.e., which is the root of the left argument of the ⊸\multimap-node), to the root of the consequent (i.e., to the ⊸\multimap-node itself) that does not contain the right argument of the ⊸\multimap-node.

Theorem 4.6. If Λ\Lambda is a correct linking on Γ⊢A\Gamma\vdash A, then there is a unique maximal linking which can be obtained from Λ\Lambda by a sequence of simple extensions.

Proof. We consider the relation ⇝ext\rightsquigarrow_{\mathrm{ext}} on linkings as a rewriting system, and we show that it is terminating and confluent. Termination follows immediately from the fact that the test of Λ\Lambda is a finite acyclic graph, and each simple extension shifts the target of a jump along an edge of the test.

Confluence is proven by showing that all critical pairs are joinable. If Λ1\Lambda_1 and Λ2\Lambda_2 are obtained by shifting two different jumps, then they are trivially joinable. If Λ1\Lambda_1 and Λ2\Lambda_2 are obtained by shifting the same jump ⟨v,w⟩\langle v,w\rangle to two different targets w1w_1 and w2w_2, then ww must have been a ⊗\otimes-node, and w1w_1 and w2w_2 must be the two children of ww, both negative nodes. Let u1u_1 and u2u_2 be the targets of a jump obtained by shifting the jump ⟨v,w1⟩\langle v,w_1\rangle and ⟨v,w2⟩\langle v,w_2\rangle respectively, until possible, and let Λ1′\Lambda'_1 and Λ2′\Lambda'_2 be the resulting linkings. We know by Remark 4.4 that u1u_1 and u2u_2 must be positive nodes, and they cannot be children of ⊗\otimes-nodes, since we can always shift the jump without violating the correctness condition 3. If, wlog, u1≠u2u_1 \ne u_2 is the positive root of Γ⊢A\Gamma\vdash A and u2u_2 is the right child of a ⊸\multimap-node, then, since Λ1′\Lambda'_1 is correct, we know that we should also be capable of safely shifting the jump ⟨v,u2⟩\langle v,u_2\rangle since there is a path from the left child of such ⊸\multimap-node to vv (passing through ww) and following the sequence of vertices we used to extend the jump ⟨v,w⟩\langle v,w\rangle to ⟨v,u1⟩\langle v,u_1\rangle. With a similar reasoning, we can show that if u1u_1 is the right child of another ⊸\multimap-node, then one between ⟨v,u1⟩\langle v,u_1\rangle and ⟨v,u2⟩\langle v,u_2\rangle can be safely shifted.

Of course, one may find a canonical proof net for a sequent Γ⊢A\Gamma\vdash A by applying the translation in Figure 5 to any derivation of Γ⊢A\Gamma\vdash A, and then by applying the simple extensions to the resulting proof net until we reach a maximal linking. However, we can also define a direct translation from sequent calculus derivations to canonical proof nets as shown in Figure 8.

Rules for the direct translation of IMLL derivations into proof nets

Figure 8 (PDF p. 15). Rules for the direct translation of IMLL derivations into proof nets replacing the corresponding rules in Figure 5, where ρ∈{⊸,⊗}\rho\in\{\multimap,\otimes\} and τ∈{⊸,⊗}\tau\in\{\multimap,\otimes\}. By max⁡(Λ)\max(\Lambda) we denote the maximal linking obtained from Λ\Lambda by applying simple extensions.

Example 4.7. Below on the left, we show the the translation of a derivation into a canonical proof net using the translation in Figure 8, and on the right we show the translation of the same derivation into a non-canonical proof net using the translation in Figure 5. These are given by decorating each sequent in the derivation with the linking obtained by applying the translation to the derivation above the sequent.

Image not extracted

Figure 3.

Notice that in the derivation on the left, the top-most ⊗\otimes-rule and ⊸\multimap-rule shift the jumps to the ⊗\otimes-node, while in the derivation on the right the jumps are never shifted.

Proposition 4.8. Let Λ::Γ⊢A\Lambda:: \Gamma\vdash A and Λ′::Γ⊢A′\Lambda' :: \Gamma\vdash A' be two proof nets for Γ⊢A\Gamma\vdash A such that Λ′\Lambda' is a simple extension of Λ\Lambda. Then Λ::Γ⊢A\Lambda:: \Gamma\vdash A and Λ′::Γ⊢A′\Lambda' :: \Gamma\vdash A' are translations of equivalent derivations in IMLL.

Proof. It suffices to remark that each simple extension of a jump ⟨v,w⟩\langle v,w\rangle corresponds to the rule permutations in the sequent calculus moving the 1\mathbf{1}-rule introducing the node vv below the rule introducing the connective corresponding to the node ww.

We conclude the section by formally stating the main result of the paper.

Theorem 4.9 (Canonicity). Let D1\mathcal{D}_1 and D2\mathcal{D}_2 be two derivations of Γ⊢A\Gamma\vdash A in IMLL. Then D1∼D2\mathcal{D}_1 \sim\mathcal{D}_2 iff ⟦D1⟧max⁡=⟦D2⟧max⁡\llbracket\mathcal{D}_1\rrbracket^{\max} = \llbracket\mathcal{D}_2\rrbracket^{\max}.

Proof. If D1∼D2\mathcal{D}_1 \sim\mathcal{D}_2, then by definition there is a sequence of independent rule permutations from Figure 6 transforming D1\mathcal{D}_1 into D2\mathcal{D}_2. We conclude by induction on the number of these permutations, observing that rules not involving 1\mathbf{1}-rules do not change the linking, while the rule permutations involving 1\mathbf{1}-rules and moving a 1\mathbf{1}-rule below a rule changing the formula in the consequent (i.e., a ⊗\otimes, ⊸\multimap, or a ⊸\multimap-rule) correspond to simple extensions of the linking (see Proposition 4.1 and Proposition 4.8).

To prove the converse, we show by induction on the number of vertices in the test of Λ::Γ⊢A=⟦D1⟧max⁡=⟦D2⟧max⁡\Lambda:: \Gamma\vdash A = \llbracket\mathcal{D}_1\rrbracket^{\max} = \llbracket\mathcal{D}_2\rrbracket^{\max} that if it is possible to sequentialize Λ::Γ⊢A\Lambda:: \Gamma\vdash A into a derivation D1\mathcal{D}_1 and into a derivation D2\mathcal{D}_2 starting with two different rules, then there are two derivations D1′\mathcal{D}'_1 and D2′\mathcal{D}'_2 such that D1′∼D2′\mathcal{D}'_1 \sim\mathcal{D}'_2, and such that D1′\mathcal{D}'_1 and D2′\mathcal{D}'_2 only differ in the order of the last two rules, which can be permuted by one of the rule permutations in Figure 6. □

On Cut Elimination for Canonical Proof Nets

We conclude this section by briefly discussing how to define cut-elimination for canonical proof nets. Since we are defining proof nets as decorations of sequents, we have to include a connective in the language of formulas to represent a pair of cut-formulas in the sequent, and to extend the definition of test to include such connective.

The results in the previous section are straightforwardly extended to canonical proof nets with cuts, by simply considering the cut-⊸\multimap-connective as a ⊸\multimap, except for the definition of the simple extensions, where we forbid to shift the target of a jump to a cut-formula.

Definition 4.10. The cut-connective ⊸cut\overset{\mathrm{cut}}{\multimap} is a binary connective. A cut-formula is a formula of the form A⊸cutAA \overset{\mathrm{cut}}{\multimap} A where AA is a regular formula. A sequent with cuts is a sequent Γ⊢A\Gamma\vdash A where Γ\Gamma may contain cut-formulas. The cut-connective should be considered as a ⊸\multimap with respect to the definition of the polarity of formulas.

A pre-net with cuts Λ::Γ⊢A\Lambda:: \Gamma\vdash A is given by a linkings Λ\Lambda on a sequent with cuts. A simple extension of a linking Λ\Lambda on a sequent with cuts is defined as in Definition 4.3, but forbidding to shift the target of a jump to the node corresponding to the cut-connective. A linking is cut-maximal if it does not admit a simple extension that is correct, or that shift the target of a jump to a cut-formula.

A canonical net with cuts is a pre-net obtained by translating a derivation in IMLL with cuts using the translation in Figure 8 extended with the following rule for the cut rule:

Proof net with highlighted edge

Figure 8.

D1D2Λ1::Γ⊢AΛ2::A,Δ⊢CcutΛ1∪Λ2::A⊸cutA,Γ,Δ⊢C(10)\begin{aligned} \mathcal{D}_1 && \mathcal{D}_2 \\ \Lambda_1 :: \Gamma\vdash A && \Lambda_2 :: A,\Delta\vdash C \\ \mathrm{cut}\quad \Lambda_1 \cup\Lambda_2 :: A \overset{\mathrm{cut}}{\multimap} A,\Gamma,\Delta\vdash C \tag*{(10)} \end{aligned}

A pre-net with cuts is a correct if it satisfies the correctness criterion in Definition 3.6 with the following extension for the definition of the edges in (7) for the cut-connective nodes:

cut-connective\text{cut-connective}
P⊸cutN(11)P \overset{\mathrm{cut}}{\multimap} N \tag*{(11)}

We define the cut-elimination steps for canonical proof nets, which are the same as the cut-elimination steps for non-canonical proof nets, but with the additional condition that the resulting linking after performing the cut-elimination step is a simple extension of the original linking.

Λ::Γ,1⊸cut1⊢C⇝cutmax⁡(Λ)::Γ⊢CΛ::Γ,a⊸cuta⊢C⇝cutmax⁡(Λ)::Γ⊢CΛ::Γ,(A∘⊸B∘)⊸cut(A∘⊸B∘)⊢C⇝cutmax⁡(Λ)::Γ,A∘⊸cutA∘,B∘⊸cutB∘⊢CΛ::Γ,(A∘⊗B∘)⊸cut(A∘⊗B∘)⊢C⇝cutmax⁡(Λ)::Γ,A∘⊸cutA∘,B∘⊸cutB∘⊢C(12)\begin{aligned} \Lambda:: \Gamma,1 \overset{\mathrm{cut}}{\multimap} 1 \vdash C &\rightsquigarrow_{\mathrm{cut}} \max(\Lambda) :: \Gamma\vdash C \\ \Lambda:: \Gamma,a \overset{\mathrm{cut}}{\multimap} a \vdash C &\rightsquigarrow_{\mathrm{cut}} \max(\Lambda) :: \Gamma\vdash C \\ \Lambda:: \Gamma,(A^\circ\multimap B^\circ) \overset{\mathrm{cut}}{\multimap} (A^\circ\multimap B^\circ) \vdash C &\rightsquigarrow_{\mathrm{cut}} \max(\Lambda) :: \Gamma,A^\circ\overset{\mathrm{cut}}{\multimap} A^\circ,B^\circ\overset{\mathrm{cut}}{\multimap} B^\circ\vdash C \\ \Lambda:: \Gamma,(A^\circ\otimes B^\circ) \overset{\mathrm{cut}}{\multimap} (A^\circ\otimes B^\circ) \vdash C &\rightsquigarrow_{\mathrm{cut}} \max(\Lambda) :: \Gamma,A^\circ\overset{\mathrm{cut}}{\multimap} A^\circ,B^\circ\overset{\mathrm{cut}}{\multimap} B^\circ\vdash C \tag*{(12)} \end{aligned}

Notice that the last two cut-elimination step only shift the target of those jumps that had the target the positive connective of the positive cut-formula.

Proposition 4.11. Each canonical cut-elimination step on a proof net can be performed in quadratic time in the size of the proof net.

Proof. The number of jumps in the proof net is linear in the size of the sequent, and they can be shifter a number of times which is bound by the number of nodes in the test, which is also linear in the size of the sequent.

Jumpless Proof Nets

In this section, we show that, contrary to the classical case, where there cannot be a polynomial-time correctness criterion for proof nets without jumps characterizing the class of proof nets corresponding to correct proofs in MLL, such result is possible in the intuitionistic case, and we provide a proof of it. In particular, we show that it is possible to weaken the second and third condition of the correctness criterion in Definition 3.6 to obtain a correctness criterion that still characterizes proof nets for IMLL, but which does not require considering jumps.

Definition 5.1. A jumpless linking Λ\Lambda for a sequent Γ⊢A\Gamma\vdash A is a map from the negative non-unit leaves to the positive leaves of Γ⊢A\Gamma\vdash A inducing a bijection between negative and positive non-unit leaves. A jumpless net Λ::Γ⊢A\Lambda:: \Gamma\vdash A for a sequent Γ⊢A\Gamma\vdash A is a jumpless linking Λ\Lambda on Γ⊢A\Gamma\vdash A which is the restriction of a linking defined as in Figure 5 to axiomatic links, i.e., removing jumps.

Definition 5.2. Let Λ::Γ⊢A\Lambda:: \Gamma\vdash A be a pre-net for Γ⊢A\Gamma\vdash A. It is weakly correct if it satisfies the following conditions:

(1) its test is acyclic.

(2) if L⊸RL \multimap R is a sub-formula in Γ⊢A\Gamma\vdash A, then all maximal paths starting from LL ending in a positive node contains RR.

Intuitively, this weaker version of Condition 3 is due to the fact that, removing jumps, Condition 2 does not hold anymore. Then, each maximal path would then either in AA or in a 1\mathbf{1}. In particular, if all maximal paths will end in some 1\mathbf{1}’s, then we can take the greatest positive gate they reach to be intended as the right-hand side formula of the greatest derivable sequent containing the formula L⊸RL \multimap R (see the notion of empire in [5]).

To prove the fact that the weakly correct criterion characterizes jumpless nets, we need to show that the splitting lemma, which we mention in the sketch of the proof of Theorem 3.11, holds for pre-nets satisfying the weaker correctness criterion.

Lemma 5.3 (Splitting). Let Λ::Γ⊢A\Lambda:: \Gamma\vdash A be a weakly correct pre-net for a sequent Γ⊢A\Gamma\vdash A not of the form a⊢aa \vdash a and such that Γ\Gamma does not contain 1\mathbf{1} or a ⊗\otimes, and AA is not of the form N⊸PN \multimap P. Then,

(1) either there is a splitting formula P⊸NP \multimap N in Γ\Gamma, that is, Γ=Γ1,P⊸N,Γ2\Gamma= \Gamma_1, P \multimap N, \Gamma_2 and there are two disjoint sets of links Λ1\Lambda_1 and Λ2\Lambda_2 such that Λ=Λ1∪Λ2\Lambda= \Lambda_1 \cup\Lambda_2, and Λ1\Lambda_1 only contains sub-sequents of Γ1⊢P\Gamma_1 \vdash P and Λ2\Lambda_2 only contains sub-sequents of Γ2,N⊢A\Gamma_2, N \vdash A;

(2) or AA is splitting, that is, A=P1⊗P2A = P_1 \otimes P_2 and Γ=Γ1,Γ2\Gamma= \Gamma_1, \Gamma_2, and there are two disjoint sets of links Λ1\Lambda_1 and Λ2\Lambda_2 such that Λ=Λ1∪Λ2\Lambda= \Lambda_1 \cup\Lambda_2, and Λi\Lambda_i only contains sub-sequents of Γi⊢Pi\Gamma_i \vdash P_i for i∈{1,2}i \in\{1,2\}.

Proof. We consider the partial order over the subformulas in Γ⊢A\Gamma\vdash A defined by the →\to-paths in the test by letting B<CB < C if CC occurs in all →\to-paths from BB to AA in the test.

If a formulas in Γ\Gamma admits no →\to-paths to AA, then we can take the <<-maximal formula among them, which must be a splitting. It cannot be a (negative) atom by definition of →\to, and it cannot be 1‾\overline{1} nor a ⊗‾\overline{\otimes} by hypothesis on Γ\Gamma. Therefore, such maximal formula must be a ⊸\multimap-formula P⊸NP \multimap N. We conclude as in Case 1 by letting Γ1\Gamma_1 be made of those formulas in Γ\Gamma which are <<-smaller than PP.

Otherwise, the argument is similar to the one from [23]: pick any ⊸\multimap-formula P⊸NP \multimap N in Γ\Gamma and consider the set of formulas in Γ\Gamma which are smaller than P⊸NP \multimap N. If the maximal (with respect to the subformula order) formulas <<-smaller than PP are all ⊸\multimap-formulas, then we can let Γ1\Gamma_1 be made of those formulas in Γ\Gamma which are <<-smaller than PP, and we conclude as in Case 1. If there is a maximal subformula <<-smaller than PP which is not a in Γ\Gamma, then it must be a subformula of a ⊸\multimap-formula P′⊸N′P' \multimap N' in Γ\Gamma, and we can repeat the argument on P′P'. By acyclicity of the test, this process must terminate. If we found a formula P⊸NP \multimap N in Γ\Gamma such that all the maximal formulas <<-smaller than PP are formulas in Γ\Gamma, then we conclude as in Case 1. Otherwise, Γ\Gamma must contain atomic formulas only, and A=P1⊗P2A = P_1 \otimes P_2, and we conclude as in Case 2 by letting Γi\Gamma_i be made of those formulas in Γ\Gamma which are <<-smaller than PiP_i for i∈{1,2}i \in\{1,2\}.

Theorem 5.4. A pre-net is a jumpless net iff it is weakly correct.

Proof. The structure of the proof is similar to the proof of Theorem 3.11, relying on the fact that for the splitting lemma (Lemma 5.3) to hold it suffices that the pre-net satisfies the weakly-correctness criterion.

Conclusion

In this paper, we answer positively a longstanding open question about the theory of proof nets for intuitionistic linear logic:

Is it possible to define a canonical representation of proofs in IMLL (with PTIME proof translation and PTIME correctness criterion)?

To answer this question, we have defined a notion of canonical proof nets for IMLL by requiring that jumps satisfy local conditions, and we have shown that any proof net can be transformed into a canonical one by performing simple local rewriting steps with linear complexity. To this aim, we relied on Lamarche’s correctness criterion for proof nets for intuitionistic linear logic, which is a refinement of the Danos-Regnier switching criterion for classical multiplicative proof nets, and we show that the same directed paths used by the correctness criterion can be used to guide the rewriting steps to transform a general proof net into a canonical one.

Implications and Future Work. As a consequence of our canonicity result, the same approach could be used to define canonical proof nets for the multiplicative exponential fragment of intuitionistic linear logic (IMELL). This also opens to the possibility of defining canonical proof nets for fragments of (classical) multiplicative exponential linear logic (MELL) used to encode lambda calculus, addressing the current unsatisfactory situation where the syntax of proof nets for MELL requiring the mix to be taken into account.

Another curious consequence of Section 5 is that, differently from the classical case, in IMLL there is a polynomial-time correctness criterion for proof nets without jumps, which is conservative over the unit-free case. In fact, for classical proof nets, a simple correctness criterion for proof nets with units but without jumps cannot exists, and isolate fragments of classical logic admitting such criterion (see [24, 9]). This results also ensures that the category of jump-free proof nets for IMLL (with object formulas and morphisms between AA and BB are (jump-free) proof nets for A⊸BA \multimap B) is a non-trivial quotient of the category of SMCCs, which is conservative over morphisms between unit-free objects. In such a quotient, differently from free SMCCs, the following diagram from [22] commutes.

((A⊸1)⊸1)⊸1→id((A⊸1)⊸1)⊸1↘kA⊸1kA⊸1−1↙A⊸1(13)\begin{aligned} ((A \multimap\mathbf{1}) \multimap\mathbf{1}) \multimap\mathbf{1} &\xrightarrow{\mathrm{id}} ((A \multimap\mathbf{1}) \multimap\mathbf{1}) \multimap\mathbf{1} \\ &\searrow^{k_{A \multimap\mathbf{1}}} \qquad\qquad\qquad\qquad\qquad {}^{k^{-1}_{A \multimap\mathbf{1}}}\swarrow\\ &\qquad A \multimap\mathbf{1} \tag*{(13)} \end{aligned}

where kXk_X is the canonical isomorphism between from (X⊸1)⊸1(X \multimap\mathbf{1}) \multimap\mathbf{1} to XX in the free SMCC, and kX−1k_X^{-1} is its inverse. This work is licensed under the Creative Commons Attribution License. To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/ or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany.

References

  1. [1]Matteo Acclavio. Exponentially handsome proof nets and their normalization. Electronic Proceedings in Theoretical Computer Science, 353:1–25, dec 2021.DOI
  2. [2]Matteo Acclavio and Lutz Straßburger. From syntactic proofs to combinatorial proofs. In International Joint Conference on Automated Reasoning, pages 481–497. Springer, 2018.DOI
  3. [3]Matteo Acclavio and Lutz Straßburger. On combinatorial proofs for modal logic. In Serenella Cerrito and Andrei Popescu, editors, Automated Reasoning with Analytic Tableaux and Related Methods, pages 223–240, Cham, 2019. Springer International Publishing.DOI
  4. [4]Matteo Acclavio and Lutz Straßburger. Combinatorial proofs for constructive modal logic. In Alessandra Palmigiano David Fernández-Duque and Sophie Pinchinat, editors, Advances in Modal Logic, Volume 14, pages 15–36. College Publications, 2022.
  5. [5]Gianluigi Bellin. Subnets of proof-nets in multiplicative linear logic with mix. Mathematical Structures in Computer Science, 7(6):663–669, 1997.
  6. [6]Vincent Danos and Laurent Regnier. The structure of multiplicatives. 28:181–203, 1989.
  7. [7]Erik D. Demaine and Robert A. Hearn. Constraint logic: A uniform framework for modeling computation as games. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 149–162, 2008.DOI
  8. [8]Paolo Di Giamberardino and Claudia Faggian. Jump from parallel to sequential proofs: Multiplicatives. In Zoltán Ésik, editor, Computer Science Logic, pages 319–333, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.DOI
  9. [9]Raffaele Di Donna and Lorenzo Tortora de Falco. On the role of connectivity in linear logic proofs, 2025.
  10. [10]Jean-Yves Girard. Linear logic. Theoretical computer science, 50(1):1–101, 1987.DOI
  11. [11]Jean-Yves Girard. Proof-nets: the parallel syntax for proof-theory. In Logic and Algebra, pages 97–124. Routledge, 2017.DOI
  12. [12]Willem Heijltjes and Robin Houston. No proof nets for MLL with units: proof equivalence in MLL is PSPACE-complete. In Thomas A. Henzinger and Dale Miller, editors, Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS ’14, Vienna, Austria, July 14 - 18, 2014, pages 50:1–50:10. ACM, 2014.
  13. [13]Willem B. Heijltjes, Dominic J. D. Hughes, and Lutz Straßburger. Intuitionistic proofs without syntax. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–13, 2019.DOI
  14. [14]Dominic Hughes and Willem Heijltjes. Conflict nets: Efficient locally canonical mall proof nets. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’16, pages 437–446, New York, NY, USA, 2016. Association for Computing Machinery.DOI
  15. [15]Dominic J. D. Hughes. Abstract p-time proof nets for mall: Conflict nets, 2008.arxiv.org/abs/0801.2421
  16. [16]Dominic J. D. Hughes. First-order proofs without syntax, June 2019.arxiv.org/abs/1906.11236
  17. [17]Dominic J. D. Hughes and Rob J. Van Glabbeek. Proof nets for unit-free multiplicative-additive linear logic (extended abstract). In Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, LICS ’03, page 1, USA, 2003. IEEE Computer Society.
  18. [18]Dominic J. D. Hughes and Rob J. Van Glabbeek. Proof nets for unit-free multiplicative-additive linear logic. ACM Trans. Comput. Logic, 6(4):784–842, oct 2005.
  19. [19]Dominic J.D. Hughes. Proofs Without Tears: Quantum Types. Annals of Math., 164(3):1065–1076, 2006.
  20. [20]Dominic J.D. Hughes. Towards Hilbert’s 24th problem: Combinatorial proof invariants: (preliminary version). Electr. Notes Theor. Comput. Sci., 165:37–63, 2006.
  21. [21]Takehiro Ito, Erik D. Demaine, Nicholas J.A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12):1054–1065, 2011.
  22. [22]G.M. Kelly and S. Maclane. Coherence in closed categories. Journal of Pure and Applied Algebra, 1(1):97–140, 1971.
  23. [23]François Lamarche. Proof Nets for Intuitionistic Linear Logic: Essential Nets, 2008.
  24. [24]Laurent Regnier. Lambda-calcul et réseaux. PhD thesis, Paris 7, 1992.
  25. [25]Lutz Strassburger. Deep inference and expansion trees for second-order multiplicative linear logic. Mathematical Structures in Computer Science, 29(8):1030–1060, 2019.DOI

Paper details

vlnc:W_shn9xfwg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents