💻 computer science

On the role of connectivity in Linear Logic proofs

This paper introduces a geometric condition on untyped proof-structures that transforms a known necessary connectivity property into a sufficient correctness criterion for specific fragments of linear logic, thereby enabling the recovery of sequent calculus proofs and characterizing rule permutations.

Original authors: Raffaele Di Donna, Lorenzo Tortora de Falco

Published 2026-02-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Raffaele Di Donna, Lorenzo Tortora de Falco

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to organize a massive, chaotic library. In this library, books represent logical arguments, and the shelves represent how those arguments are built. For a long time, logicians have had two ways to organize these books:

The Tree Method (Sequent Calculus): This is like building a family tree. You start with a root and branch out. It's very orderly, but it forces you to make arbitrary choices about the order of branches, even if the logic doesn't care.
The Web Method (Proof-Nets): This is like a spiderweb or a subway map. The connections are direct and flexible. It's more powerful and expressive, but it's harder to tell if a web is a "real" map or just a tangled mess of string.

The paper by Raffaele Di Donna and Lorenzo Tortora de Falco is about figuring out exactly when a tangled web is actually a valid map and when it's just a mess.

The Core Problem: The "Tangled String" Test

In the world of "Linear Logic" (a specific type of math logic), there is a famous test called the Danos-Regnier criterion. Think of this test as a way to check if your web is a valid map.

The Old Rule: To be a valid map, if you pull on the strings in a specific way (called "switching"), the web must not have any loops (it must be a tree) and it must be all one single piece (connected).
The Problem: This rule works perfectly for simple logic. But when you add more complex tools to the logic (like "weakening," which is like throwing away a book you don't need, or "bottom," which is like an empty box), the web can break into multiple pieces.
The New Observation: The authors noticed that when the web breaks, it doesn't break randomly. It breaks into a specific number of pieces. Specifically, the number of disconnected pieces is always one more than the number of "empty boxes" or "thrown-away books" in the system.

They call this the ACC♯w property. It's a necessary condition: if a web is a valid proof, it must follow this rule. But here's the catch: following this rule isn't enough. You can build a fake web that follows the rule but still isn't a real proof (like a tangled string that happens to have the right number of knots but leads nowhere).

The Solution: The "No-Empty-Box" Rule

The authors asked: Is there a simple geometric rule we can add to the "number of pieces" test to make it perfect?

They found a specific type of web where the answer is yes. They call these (¬w⊗)-proof-structures.

The Analogy:
Imagine you are building a house (the proof).

The "Empty Box" (Weakening/Bottom): This is a room with no furniture, or a door that leads to nowhere.
The "Heavy Door" (Tensor/⊗): This is a heavy door that connects two rooms.

The authors discovered that if you forbid a specific bad construction—you cannot attach a heavy door to a room that is already empty or leads nowhere—then the "number of pieces" rule becomes a perfect test.

In their words: If a web has no heavy doors connected to empty rooms, and it follows the "number of pieces" rule, it is guaranteed to be a valid proof.

Why This Matters (The "Why Should I Care?" Part)

Simplifying the Complex: Usually, checking if a complex logical web is valid is incredibly hard (mathematically speaking, it's "NP-hard," meaning it gets impossible very quickly as the web grows). By identifying these specific "safe" webs (the ones without heavy doors on empty rooms), the authors found a way to check validity easily and quickly.
Understanding "Connectivity": The paper argues that "connectivity" (how many pieces a web is in) isn't just a random geometric shape; it actually tells us something deep about the logic itself. It connects the physical shape of the proof to the logical rules used to build it.
Intuitionistic Logic: They also looked at a specific type of logic used in computer science (Intuitionistic Linear Logic). They showed that for this type, the "number of pieces" rule is equivalent to a very simple requirement: the proof must have exactly one final conclusion. If you have a web with one exit, and it follows the piece-count rule, it's a valid proof.

Summary of the Journey

The Goal: Distinguish between a valid logical proof and a random tangle of logic.
The Obstacle: The standard test fails when the logic gets too complex (allowing empty rooms and discarded items).
The Discovery: There is a relationship between the number of disconnected pieces in the proof-web and the number of "discarded" items.
The Breakthrough: If you restrict the proof to a specific "safe" zone (where discarded items don't feed into heavy connections), that relationship becomes a perfect, foolproof test.
The Result: We can now easily identify valid proofs in these specific, useful fragments of logic without getting lost in the complexity.

In short, the authors found a way to use the shape of a logical argument (how many pieces it has) to prove its truth, but only for a specific, well-behaved neighborhood of logic where the rules are strict enough to prevent "bad connections."

Technical Summary: On the Role of Connectivity in Linear Logic Proofs

Problem Statement

The paper addresses the fundamental problem of correctness criteria in Linear Logic (LL). While the shift from tree-like sequent calculus proofs to graph-like proof-nets (proof-structures) is a major contribution to proof theory, determining whether an arbitrary proof-structure represents a valid logical proof remains a complex challenge.

In the purely multiplicative fragment without units ( $MLL^-$ ), the Danos-Regnier criterion (often denoted as ACC) is a well-established, necessary, and sufficient condition: a proof-structure is a proof if and only if all its "switching graphs" are acyclic and connected. However, in the presence of units ( $\mathbf{1}$ and $\bot$ ) and exponentials (the fragment $MELL$), the situation is more difficult. The property AC (acyclicity) is necessary but not sufficient for correctness in $MELL$ without the mix rule. The property ACC (acyclicity + connectivity) fails in $MELL$ due to the presence of weakening rules and the $\bot$ constant, which naturally introduce disconnected components.

The community has long known that a necessary property for a proof-structure in $MELL$ to be a proof is $ACC^\sharp_w$ : every switching graph must be acyclic, and the number of connected components must be exactly one more than the number of $\bot$ (weakening) nodes. However, this property is not sufficient for the general case (as demonstrated by counterexamples like those in Figure 3a). The paper notes that finding a feasible correctness criterion for the full fragment with units ($MLL$) is likely impossible due to the NP-hardness of provability in the constant-only multiplicative fragment.

The central question motivating this work is: What is the logical meaning of connectivity? Specifically, can the necessary property $ACC^\sharp_w$ be turned into a sufficient one by identifying specific geometric or syntactic fragments of Linear Logic where it holds?

Methodology

The authors employ a geometric approach to proof-theory, analyzing the topological properties of proof-structures (specifically their switching graphs) without relying heavily on typing constraints in the initial analysis.

Untyped Framework: The authors first develop their results in an untyped framework. They define proof-structures as directed acyclic graphs (DAGs) with specific node types (ax, cut, $\otimes$ , $\parr$ , $\bot$ , $\mathbf{1}$ , and $\bullet$ ). This allows them to isolate geometric conditions independent of formula types.
Switching Graphs and Connectivity: They utilize the concept of switching graphs (induced by selecting one premise for each $\parr$ node) to define properties like acyclicity ($AC$) and component counts ( $C^\sharp_w$ ).
The $(\neg w \otimes)$ Condition: The core methodological innovation is the introduction of a local geometric condition called $(\neg w \otimes)$ . A proof-structure satisfies this condition if no premise of a $\otimes$ $\otimes$ (tensor) or cut node is the conclusion of an "erasing" node (a $\bot$ $⊥$ , $\parr$ $\parr$ , or $\bullet$ $∙$ node whose premises are all conclusions of erasing nodes).
- Intuitively, this forbids "erasing" nodes from feeding directly into "multiplicative" nodes.
Sequentialization via Induction: The authors prove their main theorems using induction on the number of arcs in the proof-structure. They demonstrate that under the $(\neg w \otimes)$ condition, the property $ACC^\sharp_w$ guarantees the existence of a "splitting" node (a terminal cut or $\otimes$ node) that uniquely decomposes the structure, allowing for a recursive reconstruction of a sequent calculus proof.
Canonical Jumps: For fragments where the $(\neg w \otimes)$ condition does not naturally hold (or to refine the sequentialization), the authors introduce a method of adding "jumps" (arcs from $\bot$ nodes to other nodes) in a canonical position. This allows them to recover the full ACC property or establish equivalence relations between proofs.

Key Contributions and Results

1. The Main Theorem for Untyped Proof-Structures

The paper's primary result is Theorem 47:

Let $R$ be a $(\neg w \otimes)$ -proof-structure. If $R$ satisfies $ACC^\sharp_w$ (acyclic switching graphs with component count $= \# \bot + 1$ ), then $R$ is sequentializable (i.e., it corresponds to a valid sequent calculus proof).

This result establishes that $ACC^\sharp_w$ , previously known only as a necessary condition, becomes a sufficient correctness criterion for the specific class of $(\neg w \otimes)$ proof-structures.

2. Characterization of the Fragment $(\neg \bot \otimes)LL$

The authors define a typed fragment of $MLL$ called $(\neg \bot \otimes)LL$ (Definition 50), where formulae are restricted such that the conclusion of an erasing node cannot be a premise of a $\otimes$ node.

Corollary 52: For any proof-structure in this fragment, $R$ is sequentializable if and only if $R \models ACC^\sharp_w$ .
Significance: This provides a feasible correctness criterion for a fragment of $MLL$ that includes units, overcoming the complexity barriers of the full fragment.

3. Canonical Sequentialization and Proof Equivalence

In Section 4, the authors refine the sequentialization process for $(\neg \bot \otimes)LL$ .

They define a canonical position for jumps (Definition 58), denoted $\langle R \rangle^m_w$ , which assigns a specific target node to every $\bot$ node based on the structure of the proof.
Theorem 62: If a jump-free proof-structure in this fragment satisfies $ACC^\sharp_w$ , there exists a sequent calculus proof that maps to the canonical jump-total structure.
Corollary 66: This leads to a simplified decision procedure for proof equivalence (permutation of rules). Two proofs in $(\neg \bot \otimes)LL$ are equivalent if and only if their desequentializations (the underlying jump-free proof-structures) are identical. This contrasts with the full $MLL$, where this problem is PSPACE-complete.

4. Extensions to Exponentials and Intuitionistic Logic

MELL Extensions (Section 5): The results are extended to the multiplicative exponential fragment ($MELL$). The fragment $(\neg ? \otimes)LL$ (Definition 69) and the polarized fragment ( $LL_{pol}$ ) are shown to satisfy the same correctness criteria. This recovers known results for polarized proof-nets (Corollary 72).
Intuitionistic Linear Logic (Section 6): The authors investigate the intuitionistic fragment ($IMELL$). They prove that for cut-free proof-structures in the intuitionistic constant-only fragment ($ICOMLL$), the property $ACC^\sharp_w$ is equivalent to having exactly one output conclusion (Proposition 77, Theorem 82). This provides a geometric characterization of the intuitionistic requirement.

Significance and Claims

The paper claims significance in the following areas:

Geometric Interpretation of Logic: The work advances the understanding of the relationship between geometric properties (connectivity) and logical validity. It demonstrates that connectivity is not merely a technical constraint but carries specific logical meaning regarding the interaction between erasing (weakening) and multiplicative rules.
Refinement of Correctness Criteria: By isolating the $(\neg w \otimes)$ condition, the authors show that the "weak" necessary condition $ACC^\sharp_w$ is actually sufficient for a non-trivial and interesting class of proofs. This bridges the gap between the well-behaved $MLL^-$ and the complex $MELL$.
Complexity and Equivalence: The paper highlights that restricting the logical language to satisfy geometric conditions (like $(\neg w \otimes)$ ) can drastically reduce the complexity of decision problems, such as proof equivalence, moving them from PSPACE-complete to polynomial-time decidable (via simple structural equality).
Unification: The approach unifies various existing correctness criteria (including those for polarized logic and intuitionistic logic) under the umbrella of connectivity properties and component counting, suggesting a unified geometric perspective on different fragments of Linear Logic.

The authors explicitly state that their goal is "to let connectivity talk" and understand its logical implications, rather than to propose new computational applications or experimental proposals. The work is presented as a theoretical contribution to the "theory of proof-nets," focusing on the structural properties that distinguish valid proofs from arbitrary graphs.