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.
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.
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).

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 (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 -rule is to include additional edges connecting a -gate to another gate in the proof net, called jumps, to represent the connection between the -gate and the context in which it is applied.3 This makes it possible to ensure that the -gate corresponds to a valid application of the -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.

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 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 . 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) and the unit using the logic operators linear implication , and tensor as follows:
A context 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 comprises a context (the antecedent) and a formula (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
with its parse tree, which is depicted as follows:
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 or . For example, each node in the following sequent has its implication depth annotated over it:
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:
Similarly, if a sub-formula has its root node with negative variance, we may write it with a overline, for example:
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 . If is an atom, then the derivation is just an instance of ax. If is , then the derivation is an instance of followed (bottom-up) by an instance of . If is (resp. ), then the derivation is an instance of (resp. ) followed (bottom-up) by a (resp. ) with premises the sequents and , 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.

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 made of a (finite) set of vertices , and a set of edges whose elements are pairs of vertices, written or . In an edge , we call its source and 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 form a vertex to a vertex of length is a sequence of vertices such that and , and such that for all . A
cycle in is a path of positive length from a vertex to itself. A graph is a directed acyclic graph (or dag) if it contains no cycles. A tree is a dag with a single vertex (called its root) such that there is a path from any other vertex of the graph to . A leaf is a vertex which is not the target of any edge.
Notation 2.5. We depict the edges of a graph by arrows between them. For example, the graph can be represented as . 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 is a pair of nodes such that is a negative leaf. It is an axiom link if and are occurrences of the same atom, and a jump if is an occurrence of .
A linking on a sequent is a function associating a link to each negative leaf of . It is axiomatic if the restriction of 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 on it.
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
then can be written as the following set of pairs of nodes
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 and . 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 made of a sequent and a linking on .
A proof net for a sequent is the pre-net with linking induced by a derivation in IMLL with conclusion as follows:
each ax with conclusion induces an axiomatic link in ;
each -rule with conclusion induces a jump link in .
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 .
Definition 3.6. The test of a pre-net is the directed graph with vertices the nodes of , and edges defined either by the links in (marked as ) as follows:

Figure 7.
or by the sub-formula relations (marked as ) as follows:
where source and target of the edges are the root nodes of the corresponding sub-formulas.
Remark 3.7. If is a sequent, and is a negative sub-formula of , then there are always paths from to any negative leaf of the sub-tree of the parse tree of .
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 be a pre-net. It is correct if it satisfies the following conditions:
(1) its test is acyclic.
(2) for any sub-formula of .
(3) if is a (positive) sub-formula in , then any maximal path in the test starting from contains .
where by we denote the existence of a path from (the root node of) to (the root node of) in the test .
Example 3.9. The test of the linking in Equation (6) is the following graph.
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.
Theorem 3.11. A pre-net 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 of the sequent , and by checking that the linking defined by the translation of is correct.
The left-to-right direction is proved by showing that if is a correct pre-net, then we can sequentialize it, that is, we can construct a derivation of such that .
If is of the form or , then we can easily construct such derivation, which would be made of a single rule application of or ax respectively.
Similarly, if contains a unit or a -formulas, or if is a -formula, then we can apply the corresponding rule to construct a derivation of such that , and we can apply the induction hypothesis to the resulting sub-pre-net. Notice that the correctness condition 3 ensures that if is a -formula, then removing the main connective of 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 is not of the above forms, then either or a formula in 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 (by conditions 2 and 3), and that if none of the formulas in 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 in IMLL defined by the independent rule permutations. Note that for the unary-vs-binary right permutations the case -vs- is ruled out since both apply to the consequent of their sequent, and thus they cannot be independent.

Figure 6.

Figure 6 (PDF p. 12). Independent rule permutations in IMLL {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 can change the jump links, since they change the position of the jump associated to the unit introduced by the -rule (see Figure 5). For example, see Figure 1.
Proposition 4.1. Let and be two derivations in IMLL. If , the set of axiom links in and are the same, but the set of jump links in and may be different.
At the same time, it is not difficult to show that given two derivations and obtained by sequentializing the same proof net, then .
Lemma 4.2. Let and be two derivations in IMLL. If , then .
Recovering Canonicity
To recover canonicity, we use the fact that the test of a linking is a directed acyclic graph where every node admits a path to the root 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 , 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.

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 always induce a critical pair in the rewriting.
Definition 4.3. Let and be two linkings on the same sequent . We say that is a simple extension of if is obtained by shifting the target of a jump in along an edge in the test of , that is, if for some and such that there is an edge in . See Figure 7.
A linking is maximal if no simple extension of is correct. A proof net is canonical if its linking is maximal.
Remark 4.4. If is a linking on and there is a jump in with target a negative node of , then is not maximal. This is because either
is a leaf of the parse tree of , 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 is not a leaf of the parse tree of , in which case it must be either a -node or a -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:
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 -node, as shown below.
However, this would result in having a path in the test from the -node (i.e., which is the root of the left argument of the -node), to the root of the consequent (i.e., to the -node itself) that does not contain the right argument of the -node.
Theorem 4.6. If is a correct linking on , then there is a unique maximal linking which can be obtained from by a sequence of simple extensions.
Proof. We consider the relation 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 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 and are obtained by shifting two different jumps, then they are trivially joinable. If and are obtained by shifting the same jump to two different targets and , then must have been a -node, and and must be the two children of , both negative nodes. Let and be the targets of a jump obtained by shifting the jump and respectively, until possible, and let and be the resulting linkings. We know by Remark 4.4 that and must be positive nodes, and they cannot be children of -nodes, since we can always shift the jump without violating the correctness condition 3. If, wlog, is the positive root of and is the right child of a -node, then, since is correct, we know that we should also be capable of safely shifting the jump since there is a path from the left child of such -node to (passing through ) and following the sequence of vertices we used to extend the jump to . With a similar reasoning, we can show that if is the right child of another -node, then one between and can be safely shifted.
Of course, one may find a canonical proof net for a sequent by applying the translation in Figure 5 to any derivation of , 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.

Figure 8 (PDF p. 15). Rules for the direct translation of IMLL derivations into proof nets replacing the corresponding rules in Figure 5, where and . By we denote the maximal linking obtained from 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.
Figure 3.
Notice that in the derivation on the left, the top-most -rule and -rule shift the jumps to the -node, while in the derivation on the right the jumps are never shifted.
Proposition 4.8. Let and be two proof nets for such that is a simple extension of . Then and are translations of equivalent derivations in IMLL.
Proof. It suffices to remark that each simple extension of a jump corresponds to the rule permutations in the sequent calculus moving the -rule introducing the node below the rule introducing the connective corresponding to the node .
We conclude the section by formally stating the main result of the paper.
Theorem 4.9 (Canonicity). Let and be two derivations of in IMLL. Then iff .
Proof. If , then by definition there is a sequence of independent rule permutations from Figure 6 transforming into . We conclude by induction on the number of these permutations, observing that rules not involving -rules do not change the linking, while the rule permutations involving -rules and moving a -rule below a rule changing the formula in the consequent (i.e., a , , or a -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 that if it is possible to sequentialize into a derivation and into a derivation starting with two different rules, then there are two derivations and such that , and such that and 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--connective as a , 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 is a binary connective. A cut-formula is a formula of the form where is a regular formula. A sequent with cuts is a sequent where may contain cut-formulas. The cut-connective should be considered as a with respect to the definition of the polarity of formulas.
A pre-net with cuts is given by a linkings on a sequent with cuts. A simple extension of a linking 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:

Figure 8.
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:
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.
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 for a sequent is a map from the negative non-unit leaves to the positive leaves of inducing a bijection between negative and positive non-unit leaves. A jumpless net for a sequent is a jumpless linking on which is the restriction of a linking defined as in Figure 5 to axiomatic links, i.e., removing jumps.
Definition 5.2. Let be a pre-net for . It is weakly correct if it satisfies the following conditions:
(1) its test is acyclic.
(2) if is a sub-formula in , then all maximal paths starting from ending in a positive node contains .
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 or in a . In particular, if all maximal paths will end in some ’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 (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 be a weakly correct pre-net for a sequent not of the form and such that does not contain or a , and is not of the form . Then,
(1) either there is a splitting formula in , that is, and there are two disjoint sets of links and such that , and only contains sub-sequents of and only contains sub-sequents of ;
(2) or is splitting, that is, and , and there are two disjoint sets of links and such that , and only contains sub-sequents of for .
Proof. We consider the partial order over the subformulas in defined by the -paths in the test by letting if occurs in all -paths from to in the test.
If a formulas in admits no -paths to , then we can take the -maximal formula among them, which must be a splitting. It cannot be a (negative) atom by definition of , and it cannot be nor a by hypothesis on . Therefore, such maximal formula must be a -formula . We conclude as in Case 1 by letting be made of those formulas in which are -smaller than .
Otherwise, the argument is similar to the one from [23]: pick any -formula in and consider the set of formulas in which are smaller than . If the maximal (with respect to the subformula order) formulas -smaller than are all -formulas, then we can let be made of those formulas in which are -smaller than , and we conclude as in Case 1. If there is a maximal subformula -smaller than which is not a in , then it must be a subformula of a -formula in , and we can repeat the argument on . By acyclicity of the test, this process must terminate. If we found a formula in such that all the maximal formulas -smaller than are formulas in , then we conclude as in Case 1. Otherwise, must contain atomic formulas only, and , and we conclude as in Case 2 by letting be made of those formulas in which are -smaller than for .
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 and are (jump-free) proof nets for ) 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.
where is the canonical isomorphism between from to in the free SMCC, and 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]Matteo Acclavio. Exponentially handsome proof nets and their normalization. Electronic Proceedings in Theoretical Computer Science, 353:1–25, dec 2021.DOI
- [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]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]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]Gianluigi Bellin. Subnets of proof-nets in multiplicative linear logic with mix. Mathematical Structures in Computer Science, 7(6):663–669, 1997.
- [6]Vincent Danos and Laurent Regnier. The structure of multiplicatives. 28:181–203, 1989.
- [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]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]Raffaele Di Donna and Lorenzo Tortora de Falco. On the role of connectivity in linear logic proofs, 2025.
- [10]Jean-Yves Girard. Linear logic. Theoretical computer science, 50(1):1–101, 1987.DOI
- [11]Jean-Yves Girard. Proof-nets: the parallel syntax for proof-theory. In Logic and Algebra, pages 97–124. Routledge, 2017.DOI
- [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]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]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]Dominic J. D. Hughes. Abstract p-time proof nets for mall: Conflict nets, 2008.arxiv.org/abs/0801.2421
- [16]Dominic J. D. Hughes. First-order proofs without syntax, June 2019.arxiv.org/abs/1906.11236
- [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]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]Dominic J.D. Hughes. Proofs Without Tears: Quantum Types. Annals of Math., 164(3):1065–1076, 2006.
- [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]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]G.M. Kelly and S. Maclane. Coherence in closed categories. Journal of Pure and Applied Algebra, 1(1):97–140, 1971.
- [23]François Lamarche. Proof Nets for Intuitionistic Linear Logic: Essential Nets, 2008.
- [24]Laurent Regnier. Lambda-calcul et réseaux. PhD thesis, Paris 7, 1992.
- [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

