💻 computer science

Ordered Adjoint Logic (Extended Version)

This paper generalizes prior work on ordered logics by introducing a system of adjoint modalities that combines logics with varying structural properties like weakening and contraction, proving that the resulting sequent calculus admits cut elimination and that its natural deduction formulation supports decidable proof checking.

Original authors: Sophia Roshal, Frank Pfenning

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sophia Roshal, Frank Pfenning

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 managing a very strict, high-security warehouse. In this warehouse, every item (a "resource") has a specific set of rules about how it can be handled. Some items can be duplicated, some can be thrown away, some can be moved around freely, and others must be used exactly once and in a specific order.

For a long time, computer scientists have built "logics" (mathematical rulebooks) to manage these items. However, most rulebooks were too rigid. They either allowed items to be moved anywhere (like a messy room) or forced them to stay in a strict line with no flexibility.

The Problem: The "One-Size-Fits-All" Bottleneck
Previous attempts to mix these rules (like the work by Kanovich et al.) tried to solve this by having a "base mode"—a default, super-strict zone where everything happens. To do anything flexible, you had to pack up your items, move them into this strict zone, do your work, and then move them back out. It was like having to go through a security checkpoint just to grab a pen from your desk. It was clunky and required constant switching.

The Solution: Ordered Adjoint Logic
Sophia Roshal and Frank Pfenning propose a new system called Ordered Adjoint Logic. Think of this not as a single warehouse, but as a smart, multi-level logistics network.

Here is how their new system works, using simple analogies:

1. The "Modes" are Different Zones

Instead of one strict base zone, imagine a building with different floors, or "modes."

Floor A (Strict): Items here must be used exactly once, in order, and cannot be moved.
Floor B (Flexible): Items here can be copied, thrown away, or shuffled around.
Floor C (Directional): Items here can move left but not right, or vice versa.

In this new system, you don't have to force everything into one strict zone. You can work natively on the floor that fits your needs.

2. The "Elevators" (Adjoint Modalities)

The magic of their system is the elevator. They use special "shift" operators (called adjoints) to move items between floors.

If you have a flexible item but need to use it in a strict zone, you take the elevator down.
If you have a strict item but need to use it in a flexible zone, you take the elevator up.

This is much smoother than the old "base mode" approach because you only take the elevator when you absolutely need to switch contexts. You stay on your native floor as long as possible.

3. The "One-Way Streets" (Directional Mobility)

This is the paper's biggest innovation. In previous systems, if an item could move, it could usually move in both directions (left and right).

Roshal and Pfenning realized that sometimes you only need to move things one way.

The Security Analogy: Imagine a security clearance badge.
- Authorization (Left Mobile): You can get your security clearance before you start your high-security task. You can move the "authorization" item to the left of the "task" item.
- The Task (Right Mobile): You can perform the high-security task after the authorization. You can move the "task" item to the right.
- The Constraint: You cannot move the task before the authorization.

Their system allows for Left Mobility (moving left) and Right Mobility (moving right) as separate, independent rules. This lets them model complex real-world protocols (like security checks) much more accurately than before.

4. The "Traffic Cop" (Cut Elimination)

In logic, "cut elimination" is like proving that a traffic cop isn't needed to direct traffic; the cars can navigate the intersection on their own without crashing.

The authors proved that their new, complex system of elevators and one-way streets is stable. Even with all these different rules, you can always simplify a proof (a path through the warehouse) to its most direct form without getting stuck or creating contradictions. This proves the system is mathematically sound.

5. The "Automated Inspector" (Decidability)

Finally, they created a "Natural Deduction" version of this system. Think of this as an automated inspector for code.

In the old systems, checking if a program followed the rules was easy.
In this new, complex system, checking if a program is valid is harder because the inspector has to guess where items might have moved (due to mobility) or been copied (due to weakening).
The Result: The authors proved that this inspector always finishes its job. It won't get stuck in an infinite loop. It can always decide, "Yes, this code is valid" or "No, it breaks the rules," even though the rules are very subtle and hidden.

Summary

Roshal and Pfenning built a new, flexible rulebook for managing resources in computer programs.

No more clunky switching: You work natively in your specific "mode" and only switch when necessary.
One-way streets: They introduced the ability to control movement directionally (left vs. right), which is crucial for security and ordering.
It works: They proved the math holds up (no crashes) and that a computer can always check if a program follows these complex rules.

This provides a solid foundation for building programming languages that can enforce very fine-grained rules about how data is used, moved, and secured, without the system becoming too messy to understand or verify.

Technical Summary of "Ordered Adjoint Logic"

Problem Statement
Ordered logics and type systems are essential for applications ranging from computational linguistics to security protocol enforcement, where the order of resource usage is significant. In most formulations, ordered types are also linear, requiring resources to be used exactly once. While prior work by Kanovich et al. investigated calculi relaxing this constraint via subexponentials within a linear ordered logic, this approach relies on a "base mode" where all inferences occur. For ordered logics, this base mode must prohibit all structural rules (weakening, contraction, exchange), forcing applications to frequently switch in and out of this restrictive mode. Furthermore, existing subexponential systems do not fully explore the possibility of one-sided structural properties (e.g., left mobility without right mobility). The authors aim to generalize these frameworks to support a preorder of modes with varying, fine-grained structural properties—including independent control over weakening, left/right contraction, and left/right mobility—without relying on a single restrictive base mode.

Methodology
The authors introduce Ordered Adjoint Logic, a system that combines the structural flexibility of adjoint modalities with the ordering constraints of ordered logics. The methodology proceeds in two main stages:

Sequent Calculus Formulation:
The authors define a sequent calculus where antecedents are ordered sequences of labeled hypotheses. Structural rules are not global but are governed by a preorder of modes ( $k \geq m$ ). Each mode $m$ is associated with a set of structural properties $\sigma(m) \subseteq \{W, C, M_{\leftarrow}, M_{\rightarrow}\}$ (Weakening, Contraction, Left Mobility, Right Mobility).
- Shift Modalities: Instead of a base mode, the system uses shift modalities ( $\downarrow^k_m$ and $\uparrow^m_l$ ) to switch between reasoning at different modes. These shifts are derived from Benton's adjoint logic but generalized to handle ordered contexts.
- Structural Rules: The authors decompose mobility and contraction into one-sided variants. Mobility rules allow a single proposition to move arbitrarily far left or right within the antecedent sequence, provided the proposition's mode admits the corresponding directional mobility. Contraction is permitted non-locally (merging non-adjacent duplicates) to ensure cut elimination, distinct from the local contraction in standard linear logic.
- Logical Connectives: The language includes ordered implications ( $\multimap$ and $\multimap$ ), fused and twisted conjunctions, and shifts. The rules are parametric in their modes, with specific conditions ensuring the preservation of mode independence (e.g., $k \geq m \geq r$ ) when reading rules from conclusion to premises.
Natural Deduction and Decidability:
The authors transition to a natural deduction formulation where structural rules are implicit, aiming for a foundation suitable for programming languages.
- Explicit vs. Implicit: Initially, they present a system with explicit structural rules to bridge the gap with the sequent calculus. They then define a system where structural rules (weakening, contraction, mobility) are implicit.
- Algorithm for Proof Checking: To address the non-determinism introduced by implicit structural rules (specifically the unbounded application of weakening and the placement of variables in elimination rules), the authors define a "normal form" judgment ( $\Omega \gg_{\Gamma, r} \Omega_{nf}$ ). This algorithm computes the set of all possible normal forms (contexts with no repeated variables) for a given context $\Omega$ , hypothesis set $\Gamma$ , and mode $r$ .
- Set-Based Judgments: The natural deduction rules are lifted to operate on sets of normal-form contexts ( $\Xi$ ). For example, conjunction introduction computes the Cartesian product of context sets, while intersection is used for rules requiring context agreement (like additive conjunction).

Key Contributions

Generalized Adjoint Logic: The paper generalizes adjoint logic to ordered settings, introducing a preorder of modes where each mode independently controls weakening, contraction, and one-sided mobility.
One-Sided Structural Properties: The system explicitly models and proves properties for left and right mobility and contraction as separate, independent structural properties, a feature anticipated but not explored in prior subexponential work.
Cut Elimination: The authors prove that the ordered adjoint sequent calculus admits cut elimination (via multicut) and identity elimination, establishing the system as a well-behaved logical framework.
Decidability of Proof Checking: The paper provides a natural deduction system with implicit structural rules and proves that proof checking for this system is decidable. This is achieved by constructing a terminating algorithm that computes the set of normal-form contexts.

Results

Theoretical Soundness: The sequent calculus is shown to satisfy cut and identity elimination. The natural deduction system is proven sound and complete with respect to the sequent calculus.
Decidability: The algorithm for computing normal forms ( $NF_{\Gamma, r}(\Omega)$ ) is proven to terminate. Consequently, the problem of checking proofs in the implicit natural deduction system is decidable.
Substructural Subsumption: The results imply the decidability of substructural subsumption, a core component of type-checking algorithms for languages like QRTT (which uses Kripke semantics with explicit worlds).

Significance and Claims
The authors claim that Ordered Adjoint Logic provides a suitable foundation for an expressive adjoint programming language or logical framework. By decoupling structural properties from a single base mode and using adjoint shifts, the system allows for native reasoning in various disciplines (linear, ordered, unrestricted) with seamless switching. The decidability of proof checking with implicit structural rules is highlighted as a critical step toward implementing bidirectional type checkers for functional programming languages that can handle fine-grained structural properties of code. The paper notes that while the decision procedure is established, practical efficiency (e.g., avoiding exponential complexity from unnecessary weakenings) remains a subject for future optimization. The work is positioned as a direct generalization of Kanovich et al.'s subexponential ordered logic and an extension of Jang et al.'s adjoint types to include order.