Ordered Adjoint Logic

Sophia Roshal, Frank Pfenning · 2026

Read Ordered Adjoint Logic by Sophia Roshal, Frank Pfenning (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19112.txt.

Introduction

Sophia Roshal and Frank Pfenning generalise earlier work on ordered logics that relax the exactly-once resource rule. Earlier calculi used subexponentials inside a linear ordered logic; the authors instead use adjoint modalities to combine logics with different structural rules, including weakening, contraction, and mobility on each side. They show the resulting sequent calculus admits cut elimination. They also give a natural deduction version with implicit structural rules and show proof checking is decidable, making the system a base for an expressive adjoint programming language or logic framework.

Catalog record

CREATORSophia Roshal, Frank Pfenning
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90551
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.19112

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ordered Adjoint Logic Sophia Roshal, Frank Pfenning Abstract Ordered logics and type systems have been used in a variety of applications including computational linguistics, memory allocation, stream processing, logical frameworks, parametricity, and enforcing security protocols. In most formulations, ordered types are also linear, requiring each resource to be used exactly once. Prior work by Kanovich et al. has investigated calculi that relax this constraint through subexponentials within a linear ordered logic. We generalize their work by using adjoint modalities to combine logics with varying fine-grained structural properties, including weakening, left contraction, right contraction, left mobility, and right mobility. We show that the resulting sequent calculus admits cut elimination. We further provide a natural deduction formulation in which structural rules are implicit, and show that proof checking for this system is decidable. This makes it a suitable foundation for an expressive adjoint programming language or logical framework. 1 Introduction Gentzen’s original sequent calculus [ 8 ] had explicit structural rules for exchange, weakening, and contraction. If we freely allow exchange, and control the uses of weakening and contraction via an exponential modality, we obtain either classical or intuitionistic linear logic [ 9 ] . Prior to that, Lambek [ 15 ] had considered a sequent calculus that disallows exchange, driven by applications in linguistics. A combination of the ideas is natural, and has been considered for the classical [ 32 , 2 , 29 , 17 ] and intuitionistic [ 22 , 23 ] cases. The latter has found applications in logical frameworks [ 24 , 21 , 20 , 30 , 19 ] , stream processing [ 7 , 6 , 4 ] , and semantic characterization of programs via parametricity [ 1 ] . In this paper we focus on the intuitionistic variant, where we use the term ordered for logics lacking exchange. In many applications, we need to combine several forms of substructural reasoning, which has been controlled with a modality for mobility \mbox{\textexclamdown}A (effectively making A linear), and the usual {!}A that also allowing weakening and contraction [ 23 ] . This has been generalized by Kanovich et al. [ 13 , 14 ] using subexponentials [ 5 , 18 ] to give an open-ended calculus parameterized by a preorder of modes that may or may not satisfy the structural properties of mobility, weakening, and contraction. A drawback of subexponentials is that they are interpreted relative to a base mode in which all the logical inferences take place. For ordered logics, this base mode must prohibit all structural rules. As a result, applications often require switching into and out of the base mode. Benton’s LNL [ 3 ] offers a solution by allowing linear and nonlinear reasoning to be connected via two adjoint modalities. This means we can reason natively in ordinary or purely linear intuitionistic logic and employ modalities only where it is necessary to include one in the other. This has been generalized to adjoint logic [ 28 , 26 , 16 , 27 , 25 ] , essentially by applying Benton’s decomposition of the exponential of linear logic to subexponentials. A related decomposition has been applied to graded modal logic [ 11 , 31 ] , although not with explicit control of exchange as far as we are aware. In this paper we introduce ordered adjoint logic, which features a preorder of modes, each of which may or may not satisfy mobility, weakening, or contraction. Instead of a particular base mode (as with subexponentials), we use the shift modalities from adjoint logic to switch between reasoning at different modes. We further decompose mobility and contraction to be one-sided, a possibility anticipated but not explored in the subexponential sequent calculus of Kanovich et al. [ 14 ] . We study ordered adjoint logic from two perspectives. We start with a sequent calculus and show that it satisfies cut and identity elimination, establishing its bona fides as a well-behaved logical system. We then introduce a system of natural deduction for ordered adjoint logic that generalizes the adjoint types of Jang et al. [ 12 ] , also controlling mobility. The result of this latter step is a natural deduction system that can easily be expanded to a type system for a functional programming language in which one can postulate and freely combine rather fine-grained information about the structural properties of code. This extension to programming languages would follow a bidirectional type checking discipline with the set of terms equivalent to those in a non-ordered setting. We show that the proof-checking problem for this system is decidable even when all applications of structural rules remain implicit. The same structures recur for a substructural language based on a Kripke semantics with explicit worlds called QRTT [ 10 ] , which has been applied to represent and enforce various security properties via typing. Consequently, our result applies to ensure decidability of substructural subsumption , which is at the core of the type-checking algorithm for QRTT. We present an ordered adjoint sequent calculus in section 2 . We conclude this section with proofs of cut and identity elimination. In section 3 , we introduce two natural deduction calculi: one with explicit structural rules and one where they remain implicit. We prove decidability of proof checking for the latter. 2 Ordered Adjoint Sequent Calculus In his seminal work on LNL, Benton [ 3 ] connects purely linear intuitionistic logic with ordinary intuitionistic logic with two adjoint modalities: F that includes unrestricted formulas in the linear ones, and G that includes the linear formulas in the unrestricted ones. The beauty of this approach is that, under the Curry-Howard isomorphism, one can natively program in either linear or nonlinear discipline, and switch between them only as needed. Moreover, we can recover the {!}A as F\,G\,A . This was later generalized in the form of adjoint logic [ 28 , 26 , 25 ] , which is parameterized by a preorder k\geq m of modes, each of which satisfies a set of structural properties \sigma(m)\subseteq\{\mathsf{W},\mathsf{C}\} . Here, \mathsf{W} stands for weakening , \mathsf{C} for contraction , while exchange is always assumed. Structural properties must be monotonic, that is, k\geq m implies \sigma(k)\supseteq\sigma(m) . Propositions are indexed by modes A_{m} , and F and G are generalized to shifts ({\downarrow}^{k}_{m}A_{k})_{m} and ({\uparrow}_{l}^{m}A_{l})_{m} . LNL is a special case with two modes {\mathchoice{\mathsf{U}}{\mathsf{U}}{\scriptscriptstyle\mathsf{U}}{\scriptscriptstyle\mathsf{U}}}>{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}} , \sigma({\mathchoice{\mathsf{U}}{\mathsf{U}}{\scriptscriptstyle\mathsf{U}}{\scriptscriptstyle\mathsf{U}}})=\{\mathsf{W},\mathsf{C}\} and \sigma({\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}})=\{\,\} . Furthermore, G\,A becomes {\uparrow}_{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}}^{\mathchoice{\mathsf{U}}{\mathsf{U}}{\scriptscriptstyle\mathsf{U}}{\scriptscriptstyle\mathsf{U}}}A_{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}} and F\,X becomes {\downarrow}^{\mathchoice{\mathsf{U}}{\mathsf{U}}{\scriptscriptstyle\mathsf{U}}{\scriptscriptstyle\mathsf{U}}}_{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}}X_{\mathchoice{\mathsf{U}}{\mathsf{U}}{\scriptscriptstyle\mathsf{U}}{\scriptscriptstyle\mathsf{U}}} . We make the presupposition that in a sequent \Gamma\vdash A_{m} , each antecedent B_{k} in \Gamma must satisfy k\geq m . In particular, B_{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}}\vdash A_{\mathchoice{\mathsf{U}}{\mathsf{U}}{\scriptscriptstyle\mathsf{U}}{\scriptscriptstyle\mathsf{U}}} , would be semantically unsound: via a cut we could derive both weakening and contraction for B_{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}} . We abbreviate this declaration of independence as \Gamma\geq m . Remarkably, all the logical rules are parametric in their modes. Their specific structural properties only come into play when we have to decide whether a structural rule can be applied to an antecedent. In this section we further generalize adjoint logic to account for order among antecedents. Everything explained above about adjoint logic still applies. 2.1 Structural Rules in an Ordered Setting In Gentzen’s presentation of sequent calculus, reordering of antecedents is governed by the exchange

Read the complete text