{'fraction_non_alphanumeric': 0.04761741358405966, 'fraction_numerical': 0.007126026582481184, 'mean_word_length': 4.549863518060052, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 31, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Linear Logic Properly Displayed

We introduce proper display calculi for intuitionistic, bi-intuitionistic and classical linear logics with exponentials, which are sound, complete, conservative, and enjoy cut-elimination and subformula property. Based on the same design, we introduce a variant of Lambek calculus with exponentials, aimed at capturing the controlled application of exchange and associativity. Properness (i.e. closure under uniform substitution of all parametric parts in rules) is the main interest and added value of the present proposal, and allows for the smoothest proof of cut-elimination. Our proposal builds on an algebraic and order-theoretic analysis of linear logic, and applies the guidelines of the multi-type methodology in the design of display calculi.


Introduction
Linear Logic [34] is one of the best known substructural logics, and the best known example of a resource-sensitive logic. The fact that formulas are treated as resources implies that e.g. two copies of a given assumption A guarantee a different proof-power than three copies, or one copy. From an algebraic perspective, this fact translates in the stipulation that linear conjunction and disjunction, denoted ⊗ and respectively, are not idempotent, in the sense that none of the inequalities composing the identities a ⊗ a = a = a a are valid in linear algebras. From a proof-theoretic perspective, this fact translates into the well known stipulation that unrestricted (left-and right-) weakening and contraction rules cannot be included in Gentzen-style presentations of linear logic.
However, resources might exist which are available unlimitedly; that is, having one or more copies of these special resources guarantees the same proof-power. To account for the co-existence of general and unlimited resources, the language of linear logic includes, along with the connectives ⊗ and (sometimes referred to as the multiplicative conjunction and disjunction), also additive conjunction and disjunction, respectively denoted & and ⊕, which are idempotent (i.e. A & A = A = A ⊕ A for every formula A). Moreover, the language of linear logic includes the modal operators ! and ?, called exponentials, which respectively govern the controlled application of leftand right-weakening and contraction rules for formulas under their scope, algebraically encoded by the following identities: The interplay between additive and multiplicative connectives, mediated by exponentials, is the main hurdle to a smooth proof-theoretic treatment of linear logic. Indeed, in the extant formalisms, this interplay is encoded by means of rules the parametric parts (or contexts) of which are not arbitrary, and hence closed under arbitrary substitution, but are restricted in some way. These restricted contexts create additional complications in the definition of smooth and general reduction strategies for syntactic cut-elimination. In the present paper, proof calculi for intuitionistic and classical linear logics are introduced in which all parameters in rules occur unrestricted. This is possible thanks to the introduction of a richer language in which general and unlimited resources are assigned different types, each of which interpreted by a different type of algebra (linear algebras for general resource-type terms, and (bi-)Heyting algebras or Boolean algebras for unlimited resource-type terms), and the interaction between these types is mediated by pairs of adjoint connectives, the composition of which captures Girard's exponentials ! and ? as defined connectives. The proof-theoretic behaviour of the adjoint connectives is that of standard normal modal operators. Moreover, the information capturing the essential properties of the exponentials can be expressed in the new language by means of identities of a syntactic shape called analytic inductive (cf. [40]), which guarantees that they can be equivalently encoded into analytic rules. The metatheory of these calculi is smooth and encompassed in a general theory (cf. [40,9,27]), so that one obtains soundness, completeness, conservativity, cut-elimination, and subformula property as easy corollaries of general facts. Moreover, the same general theory guarantees that these meta-properties transfer to all analytic variants of the basic framework, such as non-commutative, affine, or relevant linear logic.
The calculi introduced in the present paper are designed according to the multi-type methodology, introduced in [29,26] to provide DEL and PDL with analytic calculi based on motivations discussed in [39,28], and further developed in [27,7,30,42]. The multi-type methodology refines and generalizes proper display calculi (cf. [60, Section 4.1]) so as to extend the benefits of their meta-theory to logics, such as linear logic, inquisitive logic, DEL and PDL, which are not properly displayable in their single-type presentation, according to the characterization results given in [45,40,9]. The possibility of appealing to the general multi-type methodology in the specific case of linear logic is justified by an analysis of the algebraic semantics of linear logic, aimed at identifying the different types and their key interactions.
Structure of the paper. In Section 2, we highlight the ideas on which the approach of the present paper is based as they have occurred in the literature in linear logic and in the proof theory of neighbouring logics. Section 3 outlines the algebraic and order-theoretic environment which motivates our proposed treatment for the various linear logics which are also presented algebraically in this section. In Section 4, we introduce the syntactic counterpart of the multi-type semantic environment introduced in Section 3, in the form of a multi-type language, define translations between the single-type and the multi-type languages for linear logics, and discuss how equivalent analytic reformulations can be given of non-analytic axioms in linear logic. In Section 5, we introduce calculi for the various linear logics. In Section 6, we prove their soundness, syntactic completeness, conservativity, cut-elimination and subformula property. In Section 7, we apply the same techniques developed in the previous sections to the problem, pertaining to the field of categorial grammar, of developing flexible enough formal frameworks to account for exceptions in rules for the generation of grammatical sentences in natural language. Specifically, we introduce exponentials which control exchange and associativity in the same way in which exponentials in linear logic control weakening and contraction. We discuss conclusions and further directions in Section 8. Given that the present paper draws from many areas, we believe it might be convenient for the reader to include several appendices, each of which contains the definitions and facts from a given area which are used in the paper. Specifically, Appendix A reports on the definition of proper multi-type calculi and their meta-theorem; Appendix B on the definition of analytic inductive inequalities; Appendix C on basic definitions and facts on canonical extensions. Appendix D collects the proof of the inversion lemmas which are needed for verifying the completeness. Various derivations are collected in Appendixes E, F and G.

Precursors of the multi-type approach to linear logic
The multi-type methodology is aimed at developing analytic calculi with a uniform design and excellent properties for general classes of logics, but as we will argue in the present paper, it is particularly natural for linear logic, given that precisely the proof-theoretic, algebraic and categorytheoretic methods developed for linear logic have been the growth-bed for many key insights and ideas the multi-type methodology builds on. In the present section, we review some of these solutions with the specific aim of highlighting those aspects that anticipate the multi-type approach. Our presentation is certainly not an exhaustive survey of the literature, for which we refer to [59, 50,5].
Right from the first paper [34], Girard describes the connectives of linear logic as arising from the decomposition of classical connectives; this decomposition makes it possible to isolate e.g. the constructive versus the non-constructive behaviour of connectives, but also the linear versus the non-linear behaviour, using structural rules to capture each type of behaviour. In [37], Girard further expands on a conceptual framework of reference for these ideas, and in particular describes the linear behaviour as the behaviour of general actions, which can be performed at a cost, and the non-linear behaviour in terms of the behaviour of situations, or actions which can be performed at no cost (or the cost of which is negligible). The purpose of the exponential connectives is then to bridge the linear and the non linear behaviour, thus making the language of linear logic expressive enough to support a Gödel-type translation of intuitionistic/classical logic into linear logic.
While exponentials are essential precisely for embedding intuitionistic and classical logic into linear logic, they pose significant complications when it comes to cut-elimination and normalization, as is witnessed in the so-called Girard-Tait [35,58] approach to cut-elimination for Girard's calculus, discussed also by Melliès [50]. Indeed, due to the fact that exponentials have nonstandard introduction rules (the so-called promotion and dereliction rules), ad-hoc transformation steps need to be devised to account for the permutation of cuts on !-or ?-formulas with restricted weakening and contraction and with promotion, giving rise to cut elimination proofs which, besides being lengthier and more cumbersome, are not structured in such a way that the same uniform reduction strategy applies.
Motivated both by these technical issues and by more general questions about ways of making different logics coexist and interact with one other, in [36] Girard introduces a calculus for sequents Γ; Γ ′ ⊢ ∆ ′ ; ∆ with different maintenance zones: the classical zone Γ ′ and ∆ ′ where all structural rules are applicable, and the linear zones Γ and ∆, where the application of structural rules is limited according to the stipulations of the linear behaviour. The intended reading of the sequent above in terms of the linear logic language is then Γ, !Γ ′ ⊢ ?∆ ′ , ∆. A very similar environment is Andreoli's calculus of dyadic sequents [49], introduced to address the issues of cut elimination and proof search. The strategy underlying these solutions aims at enriching the language of the calculus in a way that accounts at the structural level for a neat separation of the linear behaviour from the non linear behaviour.
Although developed independently, Girard's and Andreoli's approach has strong similarities with Belnap's general proof-theoretic paradigm of display logic [3]. What Belnap refers to as display logic is not in fact one logical system presented as a sequent calculus, but rather a methodology refining Gentzen sequent calculi through the systematic enrichment of the logical language with an additional layer of structural connectives besides the comma. This richer environment makes it possible to enforce a neat separation of roles between introduction rules (i.e. rules introducing principal formulas) and structural rules (i.e. those rules expressed purely in terms of structural variables and structural connectives). Indeed, while introduction rules are defined along very uniform and rigid lines and only capture the most basic information on each logical connective (the polarity of each coordinate), structural rules encode most information on the behaviour of each connective and on the interaction between different connectives. Thanks to this neat separation of roles, a suitable environment is created in which the most important technical contribution of Belnap's paradigm can be stated and proved; namely, a general, smooth and robust proof strategy for cut-elimination, hinging on the design principles we summarize as follows: (a) uniform shape of introduction rules for all connectives, and (b) information on the specific behaviour of each connective encoded purely at the structural level. These ideas are very much aligned with Girard's considerations about the crucial role of structural rules (e.g. in telling the linear and non-linear behaviour apart) in the genesis of linear logic, and succeed in creating an explicit mathematical environment in which they can be developed further.
The alignment of Belnap's and Girard's programs is also reflected in Belnap's major motivation in introducing display calculi: creating a proof-theoretic environment capable of simultaneously accounting for "an indefinite number of logics all mixed together including boolean [...], intuitionistic, relevance and (various) modal logics." This motivation drives Belnap's bookkeeping mechanism "permitting control in the presence of multiple logics" which is remarkable in its elegance and power, and is based on the fact that (structural) connectives in all these logics are residuated. The engine of this bookkeeping mechanism is the property that gives display logic its name, namely the display property, requiring that for any (derivable) sequent X ⊢ Y and any substructure Z of X or Y, the sequent X ⊢ Y is provably equivalent to either a sequent of the form Z ⊢ Y ′ or of the form X ′ ⊢ Z (and exactly one of these cases occurs). Informally, a sequent calculus enjoys the display property if it is always possible to display any substructure Z of a given (derivable) sequent X ⊢ Y either in precedent position (Z ⊢ Y ′ ) or in succedent position (X ′ ⊢ Z) in a way that preserves logical equivalence.
However, when designing his display calculus for linear logic [4], Belnap derogates from his own design principle (a) and does not introduce structural counterparts for the exponentials. Without their structural counterparts, it is of course not possible to express the key properties of exponentials purely at the structural level, which also results in a violation of (b). Hence, in Belnap's calculus, these properties are still encoded in the introduction rules for ! and ?, which are hence non-standard. This latter fact is the key reason why the cut elimination theorem for Belnap's display calculus for linear logic does not make as significant an improvement in smoothness over those for previous calculi as it could have made.
Belnap's derogation has a technical reason, which stems from the fact that, when seen as operations on linear algebras (cf. Definition 3.1), the exponentials ! and ? are not residuated. Hence, if their structural counterparts were allowed in the language of Belnap's display calculus for linear logic, the resulting calculus would lose the display property, due to the fact that this property critically hinges on the presence of certain structural rules (the so-called display rules) for all structural connectives, which would be unsound in the case of exponentials, precisely due to their not being residuated. Hence, to preserve the display property for his calculus for linear logic (which is the ultimate drive for his cut-elimination metatheorem), Belnap is forced to give up on the full enforcement of design principles (a) and (b). 1 The differences in Belnap's and Girard-Andreoli's approaches reflect the tradeoff we are facing: unlike Belnap, Girard-Andreoli are not bound to a general strategy for cut-elimination (such as the one hinging on Belnap's display property), which leaves them the freedom to include exponentials at the structural level, at the price of not being able to develop a cut-elimination strategy via a meta-theorem. On the other hand, it is precisely the attempt to achieve cut-elimination via a general meta-theorem which prevents Belnap from using the full power of his design principles (a) and (b), and hence forces him to settle for a less than completely smooth cut-elimination result. Both solutions make improvements, which leave open space for further improvement.
Our way out of this empasse takes its move from Girard's initial idea about linear logic arising from the decomposition of classical and intuitionistic connectives, and is based on viewing exponentials as compositions of adjoint maps. This is indeed possible, and has been already pursued in the category-theoretic setting [6,5,50]. Benton [5], in particular, takes the environment of adjoint models (each consisting of a symmetric monoidal adjunction between a symmetric monoidal closed category and a cartesian closed category) as the semantic justification for the introduction of the logical system LNL, in which the linear and non-linear behaviour "exist on an equal footing". Benton explores several sequent calculi for LNL, some of which fail to be cut-free. His final proposal is perhaps the closest precursor of the multi-type calculus which is introduced in the present paper, in that it features both linear and nonlinear sequents, and rules indicating how to move from one to the other. However, the proof of cut elimination does not appeal to a meta-theorem, and hence does not straightforwardly transfer to axiomatic extensions of linear logic such as classical, affine or relevant linear logic [50,23,44].
In a nutshell, the approach pursued in the present paper is based semantically on some well known facts, which yield the definition of the algebraic counterparts of adjoint models. Firstly, the algebraic interpretation of ! (resp. ?) is an interior operator (resp. a closure operator) on any linear algebra L. Hence, by general order theory, the operation ! (resp. ?) can be identified with the composition of two adjoint maps: the map ι : L ։ K ! (resp. γ : L ։ K ? ) onto the range of ! (resp. ?) and the natural order-embedding e ! : K ! ֒→ L (resp. e ? : K ? ֒→ L). Secondly, the interaction between !, ⊗ and & (resp. between ?, and ⊕) can be equivalently rephrased by saying that the poset K ! (resp. K ? ) has a natural algebraic structure (cf. Proposition 3.6). Thirdly, the algebraic structures of L and K ! (resp. L and K ? ) are in fact compatible with the adjunction e ! ⊣ ι (resp. γ ⊢ e ? ) in a sense which is both mathematically precise and general (cf. proof of Proposition 3.6), and which provides the algebraic underpinning of the translation from classical and intuitionistic logic to linear logic. Interestingly, a very similar compatibility condition also accounts for the Gödel-Tarski translation from intuitionistic logic to the modal logic S4 (cf. algebraic analysis in [19,Section 3.1]).
The composite mathematical environment consisting of the algebras L, K ! and K ? together with the adjunction situations between them naturally provides the interpretation for a logical language which is polychromatic in Melliès' terminology [50], in the sense that admits terms of as many types as there are algebras in the environment. The mathematical properties of this environment provide the semantic justification for the design of the calculi introduced in Section 5, in which both display property and design principles (a) and (b) are satisfied. The change of perspective we pursue, along with Benton [5], Melliès [50], and Jacobs [44], is that this environment can also be taken as primary rather than derived. Accordingly, at least for proof-theoretic purposes, linear logic can be more naturally accommodated by such a composite environment than the standard linear algebras.

Multi-type semantic environment for linear logic
In the present section, we introduce the algebraic environment which justifies semantically the multi-type approach to linear logic which we develop in Section 5. In the next subsection, we take the algebras introduced in [51, 59] as starting point. We enrich their definition, make it more modular, and expand on the properties of the images of the algebraic interpretation of exponentials which are briefly mentioned in [59], leading to our notion of (right and left) 'kernels'. In Section 3.2, we expand on the algebraic significance of the interaction axioms between exponentials in terms of the existence of certain maps between kernels. In Subsection 3.3, we show that linear algebras with exponentials can be equivalently presented in terms of composite environments consisting of linear algebras without exponentials and other algebraic structures, connected via suitable adjoint maps. In Subsection 3.4, we report on results pertaining to the theory of canonical extensions applied to the composite environments introduced in the previous subsections. These results will be used in the development of the next sections.

Linear algebras and their kernels
preserves all finite meets, hence also the empty meet ⊤, in each coordinate.
An IL-algebra is a classical linear algebra (CL-algebra) if C. (a ⊸ 0) ⊸ 0 = a for every a ∈ L.
We will sometimes abbreviate a ⊸ 0 as a ⊥ , and write C above as a ⊥⊥ = a. CLSC-algebras reflect the logical signature of (classical) linear logic as originally defined by Girard, although no link between the exponentials is assumed, and ILP-algebras are a slightly modified version of Ono's modal FL-algebras [51, Definition 6.1]. The notion of BLSC-algebra is a symmetrization of that of ILSC-algebra, where the linear co-implication (aka subtraction, or exclusion) has been added to the signature as the left residual of , as was done in [38,59,57]. The proof-theoretic framework introduced in Section 5 will account for each of these environments modularly and conservatively.
Condition IL4 implies that ⊗ preserves all existing joins (hence all finite joins, and the empty join 0 in particular) in each coordinate, and ⊸ preserves all existing meets in its second coordinate and reverses all existing joins in its first coordinate. Hence, the following de Morgan law holds in IL-algebras: the main difference between IL-algebras and CL-algebras is captured by the following Lemma 3.2. The following de Morgan law also holds in CL-algebras: Proof. Since by definition (·) ⊥ is antitone, (a & b) ⊥ is a common upper bound of a ⊥ and b ⊥ . Condition C implies that (·) ⊥ : L → L is surjective. Hence, to prove the converse inequality, it is enough to show that if c ∈ L and a ⊥ ≤ By conditions S2 and S3, the operation ! : L → L is an interior operator on L seen as a poset. Dually, by SC2 and SC3, the operation ? : L → L is a closure operator on L seen as a poset. By general order-theoretic facts (cf. [22,Chapter 7] In what follows, we let K ! and K ? be the subposets of L identified by Range(!) = Range(ι) and Range(?) = Range(γ) respectively. Sometimes we will refer to elements in K ! as 'open', and elements in K ? as 'closed'.
It is interesting to notice the fit between the definition of the algebraic structure of the kernels given above and the translation by which intuitionistic formulas embed into linear formulas given in [34,Chapter 5] Proof. We only prove the first and second item, the proofs of the remaining items being dual to the proof of item 1. Let us show that for all a, b ∈ L, the greatest lower bound of ι(a) and ι(b) exists and coincides with ι(a & b). From b ≤ ⊤ and S2 we get !b ≤ !⊤. Hence, by S4 and the monotonicity of ⊗ in both coordinates, , since e ! : K ! ֒→ L is an order-embedding. Likewise, one shows that ι(a& b) ≤ ι(b), which finishes the proof that ι(a& b) is a common lower bound for ι(a) and ι(b).
Let us now show that ∧ ! preserves coordinatewise all existing joins in K ! . That is, if i∈I ι(a i ) exists, then for every b ∈ L, The following chain of identities holds: i∈I !a i ⊗ !b) (⊗ preserves existing joins) Hence, to finish the proof of the claim it is enough to show that Since e ! : K ! ֒→ L is injective and ! = e ! • ι, it is enough to show that Indeed, by S3, S4 and Fact 3.4, as required. By S2 and S4, ι(a) ≤ ι(⊤) = 1 for every a ∈ L, which motivates Definition 3.5 (LK4), and moreover, S3 implies that ι(0) ≤ 0, which motivates Definition 3.5 (KL5). Let us show that for all a, b, c ∈ L, This concludes the proof of item 1. As to item 2, let us assume that a ⊥⊥ = a for any a ∈ L. Then, by Definition 3.5 (LK7), which is enough to establish that the Heyting algebra K ! is a Boolean algebra.
Summing up, the axiomatization of the exponentials as interior and closure operators respectively generates a composite algebraic environment of linear logic, in which linear algebras come together with one or two other algebras, namely the kernels, which, depending on the original linear signature, can be endowed with a structure of Heyting algebras, distributive lattices or co-Heyting algebras. Moreover, the adjunctions relating the linear algebra and its kernel(s) also guarantee the natural embedding maps to enjoy the following additional properties: Proof. We only prove the identities involving e ! , the proof of the remaining ones being dual. Since ι : L ։ K ! is surjective and order-preserving, proving the required identity is equivalent to showing that, for all a, b ∈ L, e ! (ι(a)) ⊗ e ! (ι(b)) = e ! (ι(a) ∧ ! ι(b)) and e ! (ι(⊤)) = 1.
which are true by S4.

The interaction of exponentials in paired linear algebras
Proposition 3.8.
1. The following are equivalent in any ILSC-algebra L: 2. If L is also a BLSC-algebra, then the following are equivalent: Proof. We only prove item 1, the proof of item 2 being order-dual. Clearly, (a) and (b) are equivalent by IL4. Let us assume (c), and let a, b, c ∈ L such that b ≤ !a ⊸ ?c. Then by SC2, The following proposition develops and expands on [51, Lemma 6.1(6)] Proof. We only prove item 1, the proof of (the second part of) item 2 being order-dual. Let a, b, c ∈ L. By IL2 and IL4, it is enough to show that if !a ≤ b ⊸ ?c then !a ≤ ?b ⊸ ?c. Indeed, by the assumption, S3, S2, P, and SC3, as required.
Proposition 3.9 and the two items (c) of Proposition 3.8 imply that in any ILP-algebra (resp. BLP-algebra) L, a binary map (resp. binary maps) can be defined such that, for any α ∈ K ! and ξ ∈ K ? , the element α ⊲ ξ ∈ K ? (resp. α ◮ ξ ∈ K ? ) is the unique solution to the following equation(s): Proposition 3.10.

For any ILP-algebra L,
(a) the map ⊲ preserves finite meets in its second coordinate and reverses finite joins in its first coordinate.

For any BLP-algebra L,
(a) the map ◮ preserves finite joins in its second coordinate and reverses finite meets in its first coordinate.
(⊸ preserves meets in 2nd coord.) The verification that ⊲ reverses finite joins in its first coordinate is similar, and makes use of e ! preserving existing joins and ⊸ reversing joins in its first coordinate. As to (b), let a, b ∈ L. Since L is an ILP-algebra, axiom P holds (cf. Definition 3.1): (e ? order-embedding)

Reverse-engineering exponentials
In the previous subsections, we have seen that certain mathematical structures (namely, the kernels and their adjunction situations, and the maps ⊲ and ◮ ) arise from the axiomatization of linear algebras with exponentials. In the present subsection, we take these mathematical structures as primary (we call them heterogeneous algebras, adopting the terminology of [8]), and capture linear algebras with exponentials in terms of these. The results of the present subsection establish the equivalence between the multi-type and the standard (single-type) algebraic semantics for linear logic, and hence provide the mathematical justification for taking the multi-type semantics as primary.
Heterogeneous algebras for the various linear logics can be understood as the algebraic counterparts of Benton's LNL-models [5,Definition 9], and the identities and inequalities defining them can be understood as the multi-type counterparts of the identities defining the algebraic behaviour of exponentials. The latter understanding will be developed further in Section 4.
An heterogeneous ILS-algebra (resp. CLS-algebra) is perfect if both L and A are perfect (cf. Definition C.5).
An heterogeneous ILSC-algebra (resp. BLSC-algebra) is perfect if L, A and B are perfect (cf. Definition C.5).
3. An heterogeneous ILP-algebra is a structure (L, A, B, e ! , ι, e ? , γ, ⊲ ) such that (L, A, B, e ! , ι, e ? , γ) is an heterogeneous ILSC-algebra, and is such that, for any α ∈ A, ξ ∈ B and a, b ∈ L, An heterogeneous ILP-algebra is perfect if L, A and B are perfect (cf. Definition C.5) and ⊲ is completely meet-preserving in its second coordinate and completely join-reversing in its first coordinate.
is an heterogeneous ILP-algebra, and An heterogeneous BLP-algebra is perfect if L, A and B are perfect (cf. Definition C.5), ⊲ is completely meet-preserving in its second coordinate and completely join-reversing in its first coordinate, and ◮ is completely join-preserving in its second coordinate and completely meet-reversing in its first coordinate.
In the light of the definitions above, the results of Sections 3.1 and 3.2 can be summarized by the following: Proposition 3.12. For any algebra L, 1. If L is an ILS-algebra (resp. CLS-algebra), then (L, K ! , e ! , ι) is an heterogeneous ILS-algebra (resp. heterogeneous CLS-algebra), where K ! is as in Definition 3.5.
3. If L is an ILP-algebra, then (L, K ! , K ? , e ! , ι, e ? , γ, ⊲ ) is an heterogeneous ILP-algebra, where K ! and K ? are as in Definition 3.5, and ⊲ as indicated right after the proof of Proposition 3.9.
is an heterogeneous BLP-algebra, where K ! and K ? are as in Definition 3.5, and ⊲ and ◮ as indicated right after the proof of Proposition 3.9.
Together with the proposition above, the following proposition shows that heterogeneous algebras are an equivalent presentation of linear algebras with exponentials: Proposition 3.13. For any algebra L, 1. If (L, A, e ! , ι) is an heterogeneous ILS-algebra (resp. heterogeneous CLS-algebra), then L can be endowed with the structure of ILS-algebra (resp. CLS-algebra) defining ! : L → L by !a := e ! (ι(a)) for every a ∈ L. Moreover, A K ! .
3. If (L, A, B, e ! , ι, e ? , γ, ⊲ ) is an heterogeneous ILP-algebra, then L can be endowed with the structure of ILP-algebra by defining ! and ? as in the items above.
is an heterogeneous BLP-algebra, then L can be endowed with the structure of BLP-algebra by defining ! and ? as in the items above.
Proof. Let us prove item 1. By assumption, L is an IL-algebra (resp. CL-algebra), which verifies S1. The assumption that e ! ⊣ ι implies that both e ! and ι are monotone, and hence so is their composition !, which verifies S2. Also from e ! ⊣ ι and ι(a) ≤ ι(a) it immediately follows that !a = e ! (ι(a)) ≤ a for every a ∈ L. To finish the proof of S3, we need to show that !a ≤ !!a for every a ∈ L. By definition of !, this is equivalent to showing that e ! (ι(a)) ≤ e ! (ι(e ! (ι(a)))). By the monotonicity of e ! , it is enough to show that ι(a) ≤ ι(e ! (ι(a))), which by adjunction is equivalent to e ! (ι(a)) ≤ e ! (ι(a)), which is always true. This finishes the proof of S3. As to S4, let us observe preliminarily that, since ι is a right-adjoint, it preserves existing meets, and hence ι(⊤) = t and which, thanks to the preliminary observation, can be equivalently rewritten as follows: ) and e ! (t) = 1 which are true, by the assumptions on e ! . This completes the proof that (L, !) is an ILS-algebra.
As to the second part of the statement, let us show preliminarily that the following identities hold: Let us observe that, since e ! is a left-adjoint, it preserves existing joins, and hence e ! (f) = 0 and e ! (α ∨ β) = e ! (α) ⊕ e ! (β). Together with ι • e ! = Id A , these identities imply that which proves LK2 A and LK5 A . As to LK3 A and LK4 A , since ι preserves existing meets, and as required. As to LK6 A , let α, β ∈ A. Since A is a Heyting algebra, the inequality α ∧ (α → β) ≤ β holds. Also: Since ι is monotone and ι • e ! = Id A , this implies that: Conversely, for all α, β ∈ A, and the last inequality is clearly true. This finishes the proof of LK6 A . To show that A and K ! are isomorphic as Heyting algebras, notice that the domain of K ! is defined as K ! := Range(!) = Range(e ! • ι). Since by assumption ι is surjective, K ! = Range(e ! ), and since e ! is an orderembedding, K ! , regarded as a sub-poset of L, is order-isomorphic (hence lattice-isomorphic) to the domain of A with its lattice order. Let e ′ ! : K ! ֒→ L and ι ′ : L ։ K ! the adjoint maps arising from !. Let e : A → K ! denote the order-isomorphism between A and K ! . Thus, e ! = e ′ ! • e and ι ′ = e • ι. To finish the proof of item 1, we need to show that for all α, β ∈ A, The proof of item 2 is similar to that of item 1 and is omitted. As to item 3, to finish the proof it is enough to show that, for all a, b ∈ L, (e ? order-embedding) and the last inequality is true by assumption. The proof of item 4 is order-dual to one of item 3 and is omitted.

Canonical extensions of linear algebras and their kernels
In the previous subsection, we showed that heterogeneous algebras for the various linear logics (cf. Definition 3.11) are equivalent presentations of linear algebras with exponentials, and hence can serve as equivalent semantic structures for each linear logic, which can also be taken as the primary semantics. This change in perspective is particularly advantageous when it comes to defining the canonical extension of a linear algebra with exponential(s) in a way which uniformly applies general criteria. Indeed, the canonical extension of a normal (distributive) lattice expansion A = (L, F , G) (cf. Definition C.3) is defined in a uniform way for any signature as the normal (distributive) lattice expansion A δ := (L δ , F σ , G π ), where L δ is the canonical extension of L (cf. Definition C.1), and F σ := { f σ | f ∈ F } and G π := {g π | g ∈ G} (cf. Definition C.2).
However, since the exponentials are not normal when regarded as operations on linear algebras, when taking them as primary we do not have general guidelines in choosing whether to take the σor the π-extension of each (cf. Definition C.2), given that the σ-extensions and π-extensions of exponentials do not coincide in general, and different settings or purposes might provide different reasons to choose one extension over the other. So we would need to motivate our choice on the basis of considerations which might not easily be portable to other settings (as done in [21]).
In contrast, when defining exponentials as compositions of pairs of adjoint maps, thanks to the fact that adjoint maps are normal (in the sense of Definition C.3) in a lattice-based environment, the general criterion for defining the canonical extensions of normal lattice expansions can be straightforwardly exported to the heterogeneous algebras of Definition 3.11. Following the general guidelines, we take the σ-extensions of left adjoint maps and the π-extensions of the right adjoint maps (which are themselves adjoints, by the general theory), and then define the canonical extension of exponentials as the composition of these. Since the adjoint maps are normal and unary, they have the extra benefit of being smooth (that is, their σand π-extensions coincide cf. Section C), but this is not essential. The essential aspect is that this definition is not taken on a case-by-case basis, but rather instantiates a general criterion.
As a practical benefit of this defining strategy, we are now in a position to obtain two key properties of the identities and inequalities defining the heterogeneous algebras of Definition 3.11 as instances of general results in the theory of unified correspondence [14,18,15,52,17,16,40] for (multi-type) normal (distributive) lattice expansions. Specifically, these inequalities are all of a certain syntactic shape called analytic inductive (cf. Definition B.3). By unified correspondence theory, (analytic) inductive inequalities (1) (1) guarantees that the validity of all the identities and inequalities defining the heterogeneous algebras of the lower rows of the diagrams in the statement of Proposition 3.14 below transfers to the heterogeneous algebras in the upper rows of the same diagrams, and hence, the algebraic completeness of each original logical system transfers to the corresponding proper subclass of perfect heterogeneous algebras. Moreover, the heterogeneous algebras in the upper rows are such that all the various maps involved (including ⊲ π and ◮ σ ) are residuated in each coordinate, which implies that the display postulates relative to these connectives are sound. Property (2) guarantees that the identities and inequalities defining the heterogeneous algebras of Definition 3.11 can be equivalently encoded into (multi-type) analytic rules, which will form part of the calculi introduced in Section 5.
In what follows, we let L δ , A δ and B δ denote the canonical extensions of L, A and B respectively.
is a perfect heterogeneous ILP-algebra. Hence, is a perfect heterogeneous ILP-algebra. Hence, not only ⊲ π has residuals as in the item above, but also Proof. As to item 1, it is a basic fact (cf. Section C) that e ! ⊣ ι implies that e σ ! ⊣ ι π . This in turn implies that ι π (e σ ! (υ)) ≤ υ for every υ ∈ A δ . The converse inequality υ ≤ ι π (e σ ! (υ)) also holds, since the original inequality α ≤ ι(e ! (α)) is valid in A and is analytic inductive (cf. Definition B.3), and hence canonical (cf. Theorem B.4). The identity e σ ! (t ! ) = 1 clearly holds, since A and L are subalgebras of A δ and L δ respectively, e σ ! coincides with e ! on A and e ! (t ! ) = 1. Finally, the two inequalities e ! (α) ⊗ e ! (β) ≤ e ! (α ∧ β) and e ! (α ∧ β) ≤ e ! (α) ⊗ e ! (β) are also analytic inductive, hence canonical, which completes the proof that (L δ , A δ , e σ ! , ι π ) is an heterogeneous ILS-algebra (resp. CLS-algebra), which is also perfect, since L δ and A δ are perfect (cf. Section C). The remaining items are proved in a similar way, observing that all the inequalities mentioned in these statements are analytic inductive (cf. Definition B.3), hence canonical. The existence of the residuals of ⊲ and ◮ , as well as the claim that the heterogeneous algebras are perfect, can be argued as follows: by a proof analogous to the proof of the first (resp. second) item (b) of Proposition 3.10, one shows that ⊲ (resp. ◮ ) is finitely meet-preserving (resp. join-preserving) in its second coordinate and finitely join-reversing (resp. meet-reversing) in its first coordinate. As discussed in Section C, this implies that ⊲ π (resp. ◮ σ ) is completely meet-preserving (resp. join-preserving) in its second coordinate and completely join-reversing (resp. meet-reversing) in its first coordinate. Since these maps are defined between complete lattices, this is sufficient to infer the existence of the required residuals.
The following is an immediate consequence of Propositions 3.12, 3.13 and 3.14.

Multi-type Hilbert-style presentation for linear logic
In Section 3.3, the heterogeneous algebras associated with the various linear logics have been introduced (cf. Definition 3.11) and shown to be equivalent presentations of linear algebras with exponentials. These constructions motivate from a semantic perspective the syntactic shift we take in the present section, from the original single-type language to a multi-type language. Indeed, the heterogeneous algebras of Definition 3.11 provide a natural interpretation for the following multi-type language L MT , 2 defined by simultaneous induction from a given set AtProp of atomic propositions (the elements of which are denoted by letters p, q): 3 The interpretation of L MT -terms into heterogeneous algebras of compatible signature is defined as the straightforward generalization of the interpretation of propositional languages in algebras of compatible signature. The toggle between linear algebras with exponentials and heterogeneous algebras (cf. Sections 3.1, 3.2 and 3.3) is reflected syntactically by the following translation (·) t : L → L MT between the original language(s) L of linear logic(s) and (their corresponding multi-type languages) L MT : Not only does the translation (·) t : L → L MT elicit the switch from the single-type language to the multi-type language, but is also compatible with the underlying toggle between linear algebras with exponentials and their associated heterogeneous algebras. Indeed, for every L-algebra L, let L * denote its associated heterogeneous algebra (cf. Proposition 3.12). The following proposition is proved by a routine induction on L-formulas, using the deduction-detachment theorem of linear logic.
The main technical difference between the single-type and the multi-type settings is that, while ! and ? are not normal (i.e. their algebraic interpretations are not finitely join-preserving or meetpreserving), all connectives in L MT are normal, which allows to apply the standard proof-theoretic treatment for normal connectives to them (e.g. to associate each connective to its structural counterpart, have sound display rules etc.), according to the general definitions and results of multi-type algebraic proof theory [42]. In particular, the general definition of analytic inductive inequalities can be instantiated to inequalities in the L MT -signature (cf. Definition B.3). Hence, we are now in a position to translate the identities and inequalities for the interpretations of the exponentials in linear algebras into L MT using (·) t , and verify whether the resulting translations are analytic inductive.
It is easy to see that (iii), (iv), (vii) and (viii) are the only analytic inductive inequalities of the list above. Indeed, recall (cf. Definition B.3) that e ! , γ, ⊗, & and (resp. e ? , ι, , ⊕ and ⊸) are Fconnectives (resp. G-connectives), since their interpretations preserve finite joins (resp. meets) in each positive coordinate and reverse finite meets (resp. joins) in each negative coordinate. 4 Then (i) and (ii) violate analyticity because of ι occurring in the scope of e ! in the right-hand side, (v) and (vi) because of γ occurring in the scope of e ? in the left-hand side, and (ix) and (x) because of the subterms e ? γA and e ! ιA respectively.
In the light of the general result characterizing analytic inductive inequalities as exactly those equivalently captured by analytic rules of proper display calculi (cf. [40,Propositions 59 and 61]), the failure of the inequalities above to be analytic inductive gives a clear identification of the main hurdle towards the definition of a proper display calculus for linear logic.
However, the order-theoretic analysis developed in Section 3 also provides a pathway to a solution: Proposition 4.2. Each (in)equality in the left column of the following table is semantically equivalent on heterogeneous algebras of the appropriate signature to the corresponding (in)equality in the right column: Proof. The proof of the equivalence of the identities in the rows from the first to the fourth immediately follows from the fact that the map ι (resp. γ) is surjective and preserves finite meets (resp. joins). The equivalences of the last two rows are shown in the proof of Proposition 3.13.
The identities and inequalities in the right column of the statement of Proposition 4.2 can be then taken as an alternative multi-type Hilbert-style presentation of the ({!, ?}-fragment of) linear logic. Finally, it is easy to verify that these identities and inequalities are all analytic inductive (cf. Definition B.3), and hence can be equivalently encoded into analytic rules of a proper (multitype) display calculus. In the next section, we introduce the calculi resulting from this procedure.

Proper display calculi for linear logics
In the present section, we introduce display calculi for the various linear logics captured by the algebras of Definition 3.1. As is typical of similar existing calculi, the language manipulated by each of these calculi is built up from structural and operational (aka logical) term constructors. In the tables of Section 5.1, each structural symbol in the upper rows corresponds to one or two logical symbols in the lower rows. The idea, which will be made precise in Section 6.1, is that the interpretation of each structural connective coincides with that of the corresponding logical connective on the left-hand (resp. right-hand) side (if it exists) when occurring in precedent (resp. succedent) position.
The language L MT introduced in the previous section and the language introduced in the following subsection are clearly related. However, there are differences. Besides the fact that the language below has an extra layer of structural connectives, the main difference is that the pure kernel-type connectives are represented only at the structural level (as are the heterogeneous binary connectives and their residuals). 5 This choice is in line with the main aim of the present paper, which revolves around the original system of linear logic defined by Girard, and its intuitionistic and bi-intuitionistic variants. Accordingly, we include at the operational level only the connectives that are directly involved in capturing original linear formulas. Nonetheless, calculi for the logics of the various heterogeneous algebras would be easily obtainable as variants of the calculi introduced below, just by adding their corresponding standard introduction rules.

Language
In the present subsection, we introduce the language of the display calculi for the various linear logics (we will use D.LL to refer to them collectively). Below, we introduce the richest signature, i.e. the one intended to capture the linear logic of BLP-algebras. This signature includes the types Linear, !-Kernel, and ?-Kernel, sometimes abbreviated as L, K ? , and K ? respectively.
Our notational conventions assign different variables to different types, and hence allow us to drop the subscripts of the pure Kernel connectives and of the unary multi-type connectives, given that the parsing of expressions such as Π > Π and Γ is unambiguous.
• Structural and operational pure K-type connectives: • Structural and operational pure L-type connectives: • Structural and operational unary multi-type connectives: The connectives ! , ? , ! and ? are interpreted in heterogeneous algebras of appropriate signature as the maps ι, γ, e ! and e ? respectively. Exponentials in the language D.LL are defined as follows: In what follows, we will omit the subscripts of the unary modalities.
• Structural and operational binary multi-type connectives:

Rules
In what follows, structures of type Linear are denoted by the variables X, Y, Z, and W; structures of type !-Kernel are denoted by the variables Γ, ∆, Θ, and Λ; structures of type ?-Kernel are denoted by the variables Π, Σ, Ψ, and Ω. With these stipulations, in the present subsection we omit the subscripts of pure Kernel-type structural connectives and unary multi-type structural connectives.

Basic intuitionistic linear environment
• Identity and cut rules • Operational rules for multi-type unary operators

Co-intuitionistic and bi-intuitionistic variants
The calculus for the bi-intuitionistic (resp. co-intuitionistic) variant of linear logic with exponentials is defined by adding (resp. replacing the introduction rules for ⊸ with) the following introduction rules in the calculus given above:

Paired variants
Paired variants of each calculus given above (i.e. intuitionistic, co-intuitionistic, bi-intuitionistic) are defined by adding one, the other or both rows of display postulates below (depending on whether one, the other or both binary maps ⊲ and ◮ are part of the definition of the heterogeneous algebras associated with the given linear logic), and, accordingly, one, the other or both pairs of FS/co-FS rules, corresponding to the defining properties of the maps ◮ and ⊲ , respectively.
• Display postulates for multi-type binary operators • Structural rules corresponding to the pairing axioms

Classical linear variants
The propositional linear base of each calculus introduced above turns classical by adding (one or the other of) the following rules: adding which, not only the sequents (A ⊸ ⊥) ⊸ ⊥ ⊣⊢ A become derivable, but also (A ⊥) ⊥ ⊣⊢ A.

Relevant and affine variants
Relevant and affine variants of each calculus given above are defined by adding one or the other row of structural rules below: Adding both rows would erase the distinction between the multiplicative and the additive behaviour.

Linear negations as primitive connectives
In the present paper, we have taken the intuitionistic linear setting as basic and, as is usual in this setting, linear negation (and dual linear negation) are defined connectives. Namely, linear negation A ⊥ is defined as A ⊸ ⊥ and dual linear negation A 1 as A 1 (cf. [38]). However, one can alternatively stipulate that negation(s) are primitive. In this case, the following pure Lineartype structural and operational connectives need to be added to the language of D.LL: * ( ) 1

( ) ⊥
In the present subsection we discuss this alternative.

(Bi-)intuitionistic linear negations • Display postulates for linear negations
In the calculus extended with the rules above, and the following rules the sequents A ⊸ ⊥ ⊣⊢ A ⊥ and A 1 ⊣⊢ A 1 are then derivable as follows

Paired variants
In paired linear logics, either one or both heterogeneous negations α f ? ∈ K ? and ξ t ! ∈ K ! can be defined as α ⊲ f ? and ξ ◮ t ! respectively (and, at the structural level, also the 'symmetric' negations t ! α ∈ K ? and f ? ξ ∈ K ! defined as t ! ◭ α and f ? ⊳ ξ respectively). When these negations are taken as primitive, the following heterogeneous structural and operational connectives need to be added to the language of D.LL: • Display postulates for heterogeneous negations As usual, we will drop the subscripts, since the reading is unambiguous.
• Operational rules for heterogeneous negations In the calculus extended with the rules above, and the following rules the sequents α ⊲ f ? ⊣⊢ α f ? and ξ ◮ t ! ⊣⊢ ξ t ! become derivable (we omit the corresponding derivations). In this language, it becomes possible to formulate the following alternative versions of the FS/coFS rules (which are equivalent to them if the linear implications are defined connectives):

Interdefinable exponentials
A connection which is at least as strong as the one captured by the P/coP rules is encoded in the following rules: Indeed, in the presence of the rules above, P and coP are derivable as follows: Using swap-out and swap-in one can prove that the following sequents are derivable:

Classical linear negations
When negations are primitive, the classical linear propositional base can be captured by adding the following structural rules: The rules above are the counterparts of the classical Grishin rules Gri m and coGri m in the language in which negation is primitive and the two linear implications are defined. In the calculus extended accordingly, the sequents A ⊸ B ⊣⊢ A ⊥ B and A B ⊣⊢ A 1 ⊗ B are then derivable as follows: Moreover, left and right negation are interderivable: Augmenting the paired setting with the following rules: the following sequents become derivable as well.

Soundness
In the present subsection, we outline the verification of the soundness of the rules of D.LL w.r.t. the semantics of perfect heterogeneous algebras (cf. Definition 3.11). The first step consists in interpreting structural symbols as logical symbols according to their (precedent or succedent) position, 6 as indicated in the synoptic tables of Section 5.1. This makes it possible to interpret sequents as inequalities, and rules as quasi-inequalities. For example, the rules on the left-hand side below are interpreted as the quasi-inequalities on the right-hand side: The verification of the soundness of the rules of D.LL then consists in verifying the validity of their corresponding quasi-inequalities in perfect heterogeneous algebras. The verification of the soundness of pure-type rules and of the introduction rules following this procedure is routine, and is omitted. The validity of the quasi-inequalities corresponding to multi-type structural rules follows straightforwardly from two observations. First, the quasi-inequality corresponding to each rule is obtained by running the algorithm ALBA (cf. [40]) on one of the inequalities in the right column of the statement of Proposition 4.2. Below we perform an ALBA reduction on the last inequality in that list: It can be readily checked that the ALBA rewriting rules applied in the computation above (adjunction rules and Ackermann rules) are sound on perfect heterogeneous algebras. As discussed in [40], the soundness of these rewriting rules only depends on the order-theoretic properties of the interpretation of the logical connectives and their adjoints and residuals. The fact that some of these maps are not internal operations but have different domains and codomains does not make any substantial difference. The second observation is that the axioms in the right column of the statement of Proposition 4.2 are valid by construction on heterogeneous algebras of suitable similarity type (this readily follows from the results in Sections 3.1, 3.2 and 3.3), and hence in particular on perfect heterogeneous algebras. We finish this subsection by showing a one-step run of ALBA on another inequality in the statement of Proposition 4.2.

Completeness
In the present subsection, we show that the translations of the axioms and rules of Girard's calculus for linear logic (cf. [34]) are derivable in D.LL. Since Girard's calculus is complete w.r.t. the appropriate class of perfect linear algebras, and hence w.r.t their associated perfect heterogeneous algebras, this is enough to show the completeness of the version of D.LL corresponding to Girard's calculus. 7 The derivations of axioms and rules not involving exponentials are standard and we omit them. In the remainder of the present subsection, we focus on the rules involving exponentials, namely, • left (resp. right) dereliction and right (resp. left) promotion rules: • left (resp. right) weakening and left (resp. right) contraction rules: where, abusing notation, !X and ?Y denote structures which are built from formulas of the form !A and ?B respectively, using only the structural counterpart of ⊗ and . Translating these rules in the language of D.LL we obtain: where, abusing notation, X and Y denote structures which are built from formulas of the form A t and B t respectively, using only the structural counterpart of ⊗ and .
• Derivations of left-and right-dereliction: • Derivations of left-and right-weakening: For the purpose of showing that the promotion and contraction rules are derivable, it is enough to show that the following rules are derivable in D.LL.
Indeed, as discussed in Section D, left-introduction rules for F -connectives (such as diamonds) and right-introduction rules for G-connectives (such as boxes) are invertible. Hence, if e.g.
X ⊢ A , Y is derivable, using the inversion lemmas, associativity, exchange, regrouping, and display, one can show that •Γ ⊢ A , •Π is derivable for some Γ and Π. Also, if •Γ ⊢ A , •Π is derivable, then using associativity, exchange, coregrouping, display, and box-and diamond-introduction rules, one can show that In what follows, we show that the rules displayed above are derivable, which completes the proof that the promotion rules are derivable.
• Derivations of left-and right-promotion • Derivations of left-and right-contraction:

Conservativity
To argue that (each) calculus introduced in Section 5 adequately captures its associated linear logic, we follow the standard proof strategy discussed in [40,39]. Let LL denote a Hilbert-style presentation of (one of the variants of) linear logic (viz. those given in [51,59]

Cut elimination and subformula property
In the present section, we outline the proof of cut elimination and subformula property for the calculi introduced in Section 5. As discussed earlier on, these calculi have been designed so that the cut elimination and subformula property do not need to be proved via the original argument by Gentzen, but can rather be inferred from a meta-theorem, following the strategy introduced by Belnap for display calculi. The meta-theorem to which we will appeal for the calculi of Section 5 was proved in [27], and in Section A we report on a restricted version of it (cf. Theorem A.2) which is the one specifically applying to proper multi-type display calculi (cf. Definition A.1). By Theorem A.2, it is enough to verify that the calculi of Section 5 meet the conditions listed in Definition A.1. All conditions except C 8 are readily satisfied by inspecting the rules. In what follows we verify C 8 . This requires to check that reduction steps are available for every application of the cut rule in which both cut-formulas are principal, which either remove the original cut altogether or replace it by one or more cuts on formulas of strictly lower complexity.

Atomic propositions:
The cases for ⊥, ⊤, 0 are standard and similar to the one above.
Binary connectives monotone in each coordinate: A ⊗ B, A & B, A B, A ⊕ B are standard and similar to the one above.

The cases for
Binary connectives with some antitone coordinate: The case for A B is standard and similar to the one above.
Unary multi-type connectives: The cases for ξ and A are standard and similar to the ones above.

Structural control
We have argued that, because modularity is in-built in proper display calculi, embedding the proof theory of linear logic in the framework of proper display calculi helps to make the connections between linear logic and other neighbouring logics more systematic. Specifically, by adding the appropriate analytic rules to the version of D.LL corresponding to each linear logic (intuitionistic, bi-intuitionistic and classical) considered in this paper, we can capture e.g. the affine and relevant counterparts of each linear logic, while preserving all properties of the basic systems.
Moreover, fragments and expansions of linear logic can be captured in the same way, thus creating a framework which accounts for substructural logics. Finally, each of these calculi can be further embedded in richer calculi, for instance to obtain proper display calculi for dynamic epistemic logics on substructural propositional bases. 8 Establishing these connections is very useful for transferring techniques, insights and results from one logical setting to another. In the present section, we give one example of this transfer of techniques from linear logic to categorial grammar in linguistics.
In categorial grammar, the proof-theoretic framework of Lambek calculus and some of its extensions are used for generating grammatically well-formed sentences in natural language by means of logical derivations. One crucial problem in this area is accounting for the fact that grammar rules often admit exceptions, understood as rules which yield grammatically non well-formed constructions if applied unrestrictedly, but grammatically well-formed sentences if applied in a controlled way. In [46], Kurtonina and Moortgat propose a proof-theoretic framework which accounts for the controlled application of associativity, commutativity and their combination (among others). Their proposal is conceptually akin to the exponentials in linear logic. Indeed, the basic language of their proposal is an expansion of the basic Lambek calculus with two modal operators adjoint to one another, inspired to the modal operators into which ! decomposes. In fact, the requirements on the modal operators of [46] would perfectly match the multi-type modal operators introduced in the present paper, were it not for the fact that they are captured algebraically as operations internal to an FL-algebra, rather than having different algebras as domain and codomain. That is, Kurtonina and Moortgat adopt a single-type environment. In what follows, we recast (a fragment of) Kurtonina and Moortgat's framework for structural control in a multi-type setting.
We consider three different multi-type environments, each of which includes two types: a General type (corresponding to Lambek calculus), and a Special type, corresponding to associative, commutative, and associative+commutative Lambek calculus, respectively. The three environments have the same language, specified as follows: The language above is interpreted into algebraic structures (L, A, , ) such that: FL1. L = (L, ≤, ⊗, →, → ) is a partially ordered algebra; is a partially ordered algebra; FL5. : L → A and : A → L are such that ⊣ and = Id A ; FL6. α ⊗ β = (α ⊙ β) for for all α, β ∈ A.
Structures (L, A, , ) satisfying FL1-FL6 will be referred to as heterogeneous FL-algebras. Any such structure is associative if in addition 8 In the present paper we have treated the environment of distributive linear logic with exponentials. However, general linear logic with exponentials can be accounted for by treating the additive connectives as done in [41], where a proper display calculus is introduced for the logic of general lattices. Again, we wish to stress that it is the modularity of proper display calculi which makes it possible to obtain straightforwardly proper display calculi for general (i.e. nondistributive) linear logic by conjoining the treatment of multiplicative connectives and exponentials developed in the present paper to the treatment of additive connectives developed in [41]. and is commutative if With an argument similar to the one given in Proposition 3.13, one shows that any heterogeneous FL-algebra gives rise to an algebra L = (L, ≤, ⊗, →, → , !) such that L = (L, ≤, ⊗, →, → ) satisfies FL1 and FL2, and ! : L → L defined as !a := a satisfies S2 and S3. With the help of ! (or, equivalently, of ), the controlled commutativity and associativity in L can be expressed as follows: which corresponds to the full internal labelling discussed in [46,Section 3.2]. A basic multi-type display calculus D.FL can be straightforwardly introduced along the lines of D.LL in the following language: The rules of D.FL include identity axioms for atomic formulas (of General type), cut rules for both types, display postulates for the pure-type connectives modelled on conditions FL2 and FL4, display postulates for the multi-type connectives modelled on FL5, standard introduction rules for all connectives, 9 and the following regrouping/co-regrouping rule, which captures FL6: The associative, commutative, and associative + commutative extensions of the basic calculus D.FL are respectively defined by adding one, the other or both of the following rules, which hold unrestricted in the appropriate Special type: Then, the appropriate extension of D.FL derives the restricted associativity and commutativity holding in the General type using the interaction between regrouping and co-regrouping, display rules, and the unrestricted associativity and commutativity holding in the Special type: Exchange Associativity

Conclusions
Results. In the present paper, we have introduced proper display calculi for several variants of classical, intuitionistic and bi-intuitionistic linear logic, and proved soundness, syntactic completeness, conservativity, cut elimination and subformula property for each. These results are key instances of results in the wider research program of multi-type algebraic proof theory [42], which, generalizing [40,48], integrates algebraic canonicity and correspondence techniques [15,12,52,53,31,17,16,10,11,13,20,47] into structural proof theory, and is aimed at defining calculi with the same excellent properties of those introduced in the present paper for each member of a class of logics encompassing both dynamic logics (such as PAL [56], DEL [2,29], PDL [43,26], game logic [55], coalition logic [54]) and (non-distributive) substructural logics [32]. This theory guarantees, among other things, that each of the aforementioned properties transfers to calculi corresponding to fragments of the linear languages considered in the present paper, and to their analytic axiomatic extensions and expansions. As an application of the results and insights developed in the present paper, we have given a multi-type reformulation of the mathematically akin but independently motivated formal framework of [46], aimed at extending the use of exponentialtype connectives, decomposed into pairs of adjoint modal operators, for the controlled application of structural rules. In particular, we have outlined a multi-type framework in which the applications of commutativity and associativity are controlled in the same way in which applications of weakening and contraction are controlled in linear logic.

From distributive to general linear logic.
In the various linear logics treated in the present paper, additive connectives are distributive. However, general linear logics can be also accounted for in the framework of proper multi-type display calculi by treating the additive connectives as done in [41], where a proper multi-type display calculus is introduced for the logic of general lattices. Again, this can be achieved straightforwardly thanks to the modularity in-built in the design of proper multi-type display calculi.
Alternative symmetrization of intuitionistic linear logic. Closely connected to the modularity of (proper) display calculi is their symmetry. Indeed, while, in the original Gentzen calculi, the difference between e.g. the classical and the intuitionistic behaviour is captured by a restriction on the shape of sequents which entails that succedent parts are managed differently from precedent ones, display calculi sequents have the same unrestricted shape in every setting with no difference in the management of precedent and succedent parts. This is why, in the environment introduced in the present paper, it has been natural to consider linear subtraction along with linear implication. This connective makes it possible to realize a symmetrization of intuitionistic linear logic alternative to the one realized by switching to classical linear logic, and rather analogous to the one effected by switching from intuitionistic to bi-intuitionistic logic. As discussed in Section C, linear subtraction can always be interpreted in perfect intuitionistic linear algebras as the left residual of , and moreover, intuitionistic linear logic is complete w.r.t. perfect intuitionistic linear algebras. These facts imply that bi-intuitionistic linear logic, defined as the logic of bi-intuitionistic linear algebras (cf. Definition 3.1), conservatively extends intuitionistic linear logic. When it comes to the treatment of exponentials in the bi-intuitionistic setting, we have considered both Ono's interaction axiom (cf. P1 in Definition 3.1) and its symmetric version expressed in terms of (cf. BLP2 in Definition 3.1). In Section 3.2, we have showed that, while Ono's interaction axiom corresponds to the left-promotion rule (of ?), its symmetric version corresponds to the right-promotion rule (of !). Bi-intuitionistic linear logic provides an environment in which all the original rules involving exponentials are derivable (i.e. restricted weakening and contraction, promotion and dereliction rules). We conjecture that ! and ? are not necessarily interdefinable in the bi-intuitionistic linear setting as in classical linear logic. These features are interesting and deserving further investigation. In particular, the residuation between ⊣ can perhaps provide a handle towards an improvement in the understanding of the computational meaning of both connectives.

Extending the boundaries of properness.
Multi-type calculi are a natural generalization of the framework of display calculi, which was introduced by Belnap [3] and refined by Wansing [60] with the aim of providing an environment in which "an indefinite number of logics all mixed together" can coexist. The main technical motivation for the introduction of proper multi-type display calculi is that they can provide a way for circumventing the characterization theorems of [40,9], which set hard boundaries to the scope of Belnap and Wansing's proper display calculi. The results of the present paper are a case in point: indeed, linear logic with exponentials cannot be captured by a proper single type display calculus (cf. Section 4), but is properly displayable in a suitable multi-type setting. Conceptually, multi-type calculi realize a natural prosecution of Belnap's program, and one which is particularly suited to account both for frameworks (such as those of dynamic logics) characterized by the coexistence of formulas and other heterogeneous elements (such as agents, actions, strategies, coalitions, resources), and for frameworks (such as those of linear and substructural logics) characterized by the coexistence of different "structural regimes". Interestingly, both dynamic logics and substructural logics have proven difficult to treat with standard proof-theoretic techniques, and the hurdles in each of these settings can often be understood in terms of the interaction between the different components of a given logical framework (such as heterogeneous elements in various dynamic logics, and different structural regimes in various substructural logics). The multi-type methodology provides a uniform strategy to address these hurdles (and has been successful in the case of various logics) by recognizing each component explicitly as a type, introducing enough structural machinery so as to cater for each type on a par with any other type, and then capturing the interaction between different types purely at the structural level, by means of analytic rules involving multi-type structural connectives.

Further directions.
Multi-type calculi form an environment in which it has been possible to settle the question concerning the analitycity of linear logic. However, and perhaps even more interestingly, this environment also helps to clearly formulate a broad range of questions at various levels of generality, spanning from the one concerning the alternative symmetrization of linear logic discussed above, to the concrete implementation of Girard's research program on 'the unity of logic' [36]. Another such question concerns the systematic exploration of the different versions of the analytic rules which encode the pairing axioms P1 and BLP2 (cf. Definition 3.1) and make it possible to derive the non-analytic promotion/demotion rules. Indeed, these different versions are not equivalent in every setting, which opens up the possibility of making finer-grained distinctions. We conjecture that these relations can be expressed also in fragments of the languages considered in the present paper, such as the purely positive setting, along the lines of Dunn's positive modal logic [24].

A Proper multi-type display calculi and their metatheorem
For the sake of self-containedness, in the present section we report on (an adaptation of) the definitions and results of [27], from which the cut-elimination and subformula property can be straightforwardly inferred for the calculi defined in Section 5. The calculi defined in Section 5 satisfy stronger requirements than those for which the cut elimination meta-theorem [27,Theorem 4.1] holds. Hence, below we provide the corresponding restriction of the definition of quasi-proper multi-type calculus given in [27], which applies specifically to the calculi of Section 5. The resulting definition, given below, is the exact counterpart in the multi-type setting of the definition of proper display calculi introduced in [60] and generalized in [40].
A sequent x ⊢ y is type-uniform if x and y are of the same type. C 5 : Display of principal constituents. If an operational term a is principal in the conclusion sequent s of a derivation π, then a is in display. 10 The congruence relation between non active-parts in rule-applications is understood as derived from the specification of each rule; that is, we assume that each schematic rule of the system comes with an explicit specification of which elements are congruent to which (and then the congruence relation is defined as the reflexive and transitive closure of the resulting relation). Our convention throughout the paper is that congruent parameters are denoted by the same structural variables. For instance, in the rule X; Y ⊢ Z Y; X ⊢ Z the structures X, Y and Z are parametric and the occurrences of X (resp. Y, Z) in the premise and the conclusion are congruent. C 6 : Closure under substitution for succedent parts within each type. Each rule is closed under simultaneous substitution of arbitrary structures for congruent operational terms occurring in succedent position, within each type. C 7 : Closure under substitution for precedent parts within each type. Each rule is closed under simultaneous substitution of arbitrary structures for congruent operational terms occurring in precedent position, within each type. C 8 : Eliminability of matching principal constituents. This condition requests a standard Gentzen-style checking, which is now limited to the case in which both cut formulas are principal, i.e. each of them has been introduced with the last rule application of each corresponding subdeduction. In this case, analogously to the proof Gentzen-style, condition C 8 requires being able to transform the given deduction into a deduction with the same conclusion in which either the cut is eliminated altogether, or is transformed in one or more applications of the cut rule, involving proper subterms of the original operational cut-term. C 9 : Type-uniformity of derivable sequents. Each derivable sequent is type-uniform. C 10 : Preservation of type-uniformity of cut rules. All cut rules preserve type-uniformity.
Since proper multi-type display calculi are quasi-proper, the following theorem is an immediate consequence of [27,

B Analytic inductive inequalities
In the present section, we specialize the definition of analytic inductive inequalities (cf. [40,42]) to the multi-type language L MT , in the types Linear, !-Kernel and ?-Kernel (respectively abbreviated as L, K ! and K ? ), defined in Section 4 and reported below for the reader's convenience: 11 We will make use of the following auxiliary definition: an order-type over n ∈ N is an n-tuple ǫ ∈ {1, ∂} n . For every order type ǫ, we denote its opposite order type by ǫ ∂ , that is, ǫ ∂ (i) = 1 iff ǫ(i) = ∂ for every 1 ≤ i ≤ n. The connectives of the language above are grouped together into the families F := F K ! ∪ F K ? ∪ F L ∪ F MT and G := G K ! ∪ G K ? ∪ G L ∪ G MT defined as follows: For any f ∈ F (resp. g ∈ G), we let n f ∈ N (resp. n g ∈ N) denote the arity of f (resp. g), and the order-type ǫ f (resp. ǫ g ) on n f (resp. n g ) indicate whether the ith coordinate of f (resp. g) is positive (ǫ f (i) = 1, ǫ g (i) = 1) or negative (ǫ f (i) = ∂, ǫ g (i) = ∂). The order-theoretic motivation for this partition is that the algebraic interpretations of F -connectives (resp. G-connectives), preserve finite joins (resp. meets) in each positive coordinate and reverse finite meets (resp. joins) in each negative coordinate. For any term s(p 1 , . . . p n ), any order type ǫ over n, and any 1 ≤ i ≤ n, an ǫ-critical node in a signed generation tree of s is a leaf node +p i with ǫ(i) = 1 or −p i with ǫ(i) = ∂. An ǫ-critical branch in the tree is a branch ending in an ǫ-critical node. For any term s(p 1 , . . . p n ) and any order type ǫ over n, we say that +s (resp. −s) agrees with ǫ, and write ǫ(+s) (resp. ǫ(−s)), if every leaf in the signed generation tree of +s (resp. −s) is ǫ-critical. We will also write +s ′ ≺ * s (resp. −s ′ ≺ * s) to indicate that the subterm s ′ inherits the positive (resp. negative) sign from the signed generation tree * s. Finally, we will write ǫ(s ′ ) ≺ * s (resp. ǫ ∂ (s ′ ) ≺ * s) to indicate that the signed subtree s ′ , with the sign inherited from * s, agrees with ǫ (resp. with ǫ ∂ ).
Definition B.1 (Signed Generation Tree). The positive (resp. negative) generation tree of any L MT -term s is defined by labelling the root node of the generation tree of s with the sign + (resp. −), and then propagating the labelling on each remaining node as follows: For any node labelled with ℓ ∈ F ∪ G of arity n ℓ ≥ 1, and for any 1 ≤ i ≤ n ℓ , assign the same (resp. the opposite) sign to its ith child node if ǫ ℓ (i) = 1 (resp. if ǫ ℓ (i) = ∂).
Nodes in signed generation trees are positive (resp. negative) if are signed + (resp. −).

Definition B.2 (Good branch).
Nodes in signed generation trees will be called ∆-adjoints, syntactically left residual (SLR), syntactically right residual (SRR), and syntactically right adjoint (SRA), according to the specification given in Table 1. A branch in a signed generation tree * s, with * ∈ {+, −}, is called a good branch if it is the concatenation of two paths P 1 and P 2 , one of which may possibly be of length 0, such that P 1 is a path from the leaf consisting (apart from variable nodes) only of PIA-nodes 12 , and P 2 consists (apart from variable nodes) only of Skeleton-nodes.
f with n f = 2 We will refer to < Ω as the dependency order on the variables. An inequality s ≤ t is analytic (Ω, ǫ)-inductive if the signed generation trees +s and −t are analytic (Ω, ǫ)-inductive. An inequality s ≤ t is analytic inductive if is analytic (Ω, ǫ)-inductive for some Ω and ǫ.
In each setting in which they are defined, analytic inductive inequalities are a subclass of inductive inequalities (cf. [40]). In their turn, inductive inequalities are canonical (that is, preserved under canonical extensions, as defined in each setting). Hence, the following is an immediate consequence of general results on the canonicity of inductive inequalities.

C Background on canonical extensions
In the present section, we report on basic notions and facts of canonical extensions of bounded lattices which are used in the present paper. Our presentation is based on [17]. The proofs of many basic properties can be found in [33,25]. The canonical extension L δ of a (distributive) lattice L is a perfect (distributive) lattice, i.e. a complete (and completely distributive) lattice which is completely join-generated by its completely join-irreducible elements and completely meet-generated by its completely meet-irreducible elements. 13 Moreover, canonical extensions are unique up to isomorphisms fixing the original algebra. An element k ∈ L δ (resp. o ∈ L δ ) is closed (resp. open) if is the meet (resp. join) of some subset of L. Let K(L δ ) (resp. O(L δ )) be the set of closed (resp. open) elements of L δ . It is easy to see that the denseness condition in Definition C.1 implies that J ∞ (L δ ) ⊆ K(L δ ) and M ∞ (L δ ) ⊆ O(L δ ).
It is easy to see that the σand π-extensions of monotone maps are monotone. Moreover, the σ-extension of a map which preserves finite joins (resp. reverses finite meets) will preserve arbitrary joins (resp. reverse arbitrary meets). Because canonical extensions are complete lattices, this implies (cf. [22,Proposition 7.34]) that the σ-extension of any such map is a left (Galois) adjoint, that is, its right (resp. Galois) adjoint exists.
Dually, the π-extension of a map which preserves finite meets (resp. reverses finite joins) will preserve arbitrary meets (resp. reverse arbitrary joins), and hence the π-extension of any such map is a right (Galois) adjoint, that is, its left (Galois) adjoint exists.
Finally, if f : L → M and g : M → L are such that f ⊣ g, then f σ ⊣ g π . The definitions above apply also to n-ary operations which are ǫ-monotone 14 for some order type ǫ over n (cf. Section B). Indeed, let us first observe that taking order-duals interchanges closed and open elements: for every lattice L and every order-type ǫ over any n ∈ N, where From these observations it immediately follows that taking the canonical extension of a lattice commutes with taking order-duals and products, namely: (L ∂ ) δ = (L δ ) ∂ and (L 1 × L 2 ) δ = L δ 1 × L δ 2 . Hence, (L ∂ ) δ can be identified with (L δ ) ∂ , (L n ) δ with (L δ ) n , and (L ǫ ) δ with (L δ ) ǫ for any order type ǫ over n, where L ǫ := n i=1 L ǫ(i) . These identifications make it possible to obtain the definition of σand π-extensions of ǫ-monotone operations of any arity n and order-type ǫ over n by instantiating the corresponding definitions given above for monotone and unary functions. The σand πextensions of the lattice operations coincide with the lattice operations of the canonical extension.

Definition C.3. For any lattice L, an operation h on L of arity n h is normal if it is order-preserving or order-reversing in each coordinate, and moreover one of the following conditions holds: (a) h preserves finite (hence possibly empty) joins in each coordinate in which it is order-preserving and reverses finite meets in each coordinate in which it is order-reversing; (b) h preserves finite (hence possibly empty) meets in each coordinate in which it is order-preserving and reverses finite joins in each coordinate in which it is order-reversing.
A normal (distributive) lattice expansion is an algebra A = (L, F , G) such that L is a bounded (distributive) lattice and F and G are finite (possibly empty) and disjoint sets of operations on L such that every f ∈ F is normal and verifies condition (a), and every g ∈ G is normal and verifies condition (b). is the normal (distributive) lattice expansion A δ := (L δ , F σ , G π ), where L δ is the canonical extension of L (cf. Definition C.1), and F σ := { f σ | f ∈ F } and G π := {g π | g ∈ G}.
The definition above applies in a uniform way to any signature, and is motivated by the fact that, as remarked above, it preserves existing residuations/Galois connections among operations in the original signature. Another noticeable, if more technical feature of this definition is its being independent on whether the original maps are smooth (i.e. their σand π-extensions coincide). While all unary normal operations are smooth, normal operations of arity higher than 1 might not be smooth in general.
It follows straightforwardly from the facts above that the classes of linear algebras without exponentials, Heyting, co-Heyting and bi-Heyting algebras are closed under taking canonical extensions. It also follows that the canonical extension of a normal LE A is a perfect normal LE: Definition C.5. A normal LE A = (L, F , G) is perfect if L is a perfect lattice (cf. discussion above), and moreover the following infinitary distribution laws are satisfied for each f ∈ F , g ∈ G, 1 ≤ i ≤ Before finishing the present subsection, let us spell out the definitions of the extended operations.
Two facts are worth being highlighted, since they follow a pattern which is key to the conservativity argument given in Section 6.3. Firstly, the algebraic completeness of linear logic (without exponentials), intuitionistic, co-intuitionistic and bi-intuitionistic logic, and the canonical embedding of the algebras corresponding to these logics into their respective canonical extensions immediately give completeness of each of these logics w.r.t. the corresponding class of perfect normal LEs, which is condition (a) in the general conservativity argument of which the one given in Section 6.3 is an instance. Secondly, the existence of the adjoints and residuals (in each coordinate) of the extensions of the original operations provides semantic interpretation to all structural connectives (including to those the operational counterparts of which do not belong to the original signature). For instance, the canonical extension of any Heyting algebra (resp. co-Heyting algebra) is naturally endowed with a bi-Heyting algebra structure, since the finite distributivity of joins over meets (resp. meets over joins) implies complete distributivity holds in the canonical extension, which guarantees the existence of the left residual > of ∨ (resp. the right residual → of ∧) in the canonical extension. Likewise, the finite distributivity of over & in any intuitionistic linear algebra without exponentials guarantees the existence of the left residual of π in the canonical extension, which is then naturally endowed with a structure of bi-intuitionistic linear algebra without exponentials. The existence of all adjoints and residuals makes it possible to interpret the structural rules of the display calculus intended to capture each logic, and verify their soundness, which is requirement (b) in the general conservativity argument (cf. Section Section 6.3).

D Inversion lemmas
In the present section we prove the general inversion lemmas holding in any proper multi-type display calculus (cf. Definition A.1) Recall that rule R is invertible if every premise sequent of R may be derived from the conclusion sequent of R. In what follows, we fix an arbitrary multi-type signature (F , G) (generalizing the presentations of Appendixes B and C. See [40] for an extended discussion). The language for (the corresponding fragment of) the associated calculus is In what follows, we omit reference to types, and use variables x, y, z to denote structural terms of arbitrary type, and variables a, b, c to denote operational terms of arbitrary type. All sequents are understood to be type-uniform (cf. Section A). In any proper multi-type display calculus, the introduction rules for any f ∈ F and g ∈ G have the following shape (cf. [40]): H(a 1 , . . . , a n f ) ⊢ x f L f (a 1 , . . . , a n f ) ⊢ x x i ⊢ a i a j ⊢ x j | 1 ≤ i, j ≤ n f , ε f (i) = 1 and ε f ( j) = ∂ f R H(x 1 , . . . , x n f ) ⊢ f (a 1 , . . . , a n ) x i ⊢ a i a j ⊢ x j | 1 ≤ i, j ≤ n g , ε g (i) = 1 and ε g ( j) = ∂ g L g(a 1 , . . . , a n ) ⊢ K(x 1 , . . . , x n g ) x ⊢ K(a 1 , . . . , a n g ) g R x ⊢ g(a 1 , . . . , a n g ) In particular, if n f = 0 = n g , the rules f R and g L above reduce to the axioms (0-ary rules) H ⊢ f and g ⊢ K. Using these rules (and the standard introduction rules for lattice connectives), the following lemma can be proved by a routine induction on terms: Lemma D.1. In any proper multi-type display calculus, all sequents a ⊢ a are derivable.
Lemma D.2. In any proper multi-type display calculus, the left-introduction rule of any f ∈ F and the right-introduction rule of any g ∈ G are invertible.
The rule !R is derivable in D.LL as follows: All the previous axioms are derivable in D.LL as follows.

G A sneak preview: proper display calculi for general linear logic
In the present paper, we have mainly focused on the setting of distributive linear logic, i.e. we have assumed that & distributes over ⊕. However, thanks to the modularity of proper multi-type calculi, the versions of linear logic in which this assumption is dropped are properly displayable in suitable multi-type settings in which additives are treated according to what done in [41]. Linear logic formulas can be encoded in the language of such calculi via certain (positional) translations.
In what follows, we do not expand on their precise definition. 16 Below, we derive the sequents !A ⊗ !B ⊣⊢ ! (A & B) in a non-distributive version of D.LL. Also in this setting, the implicit applications of weakening and contraction internalized by the additive introductions of & are now explicitly performed via the unrestricted weakening and contraction rules W ℓ and C r respectively, which pertain to the new types.