Variants of classical linear logics are presented based on the modal version of new structural rule !?mingle instead of the known rules !weakening and ?weakening. The cut-elimination theorems, the completeness theorems and a characteristic property named the mix separation principle are proved for these logics.

Linear Logic is a branch of proof theory which provides refined tools for the study of the computational aspects of proofs. These tools include a duality-based categorical semantics, an intrinsic graphical representation of proofs, the introduction of well-behaved non-commutative logical connectives, and the concepts of polarity and focalisation. These various aspects are illustrated here through introductory tutorials as well as more specialised contributions, with a particular emphasis on applications to computer science: denotational semantics, lambda-calculus, logic programming and (...) concurrency theory. The volume is rounded-off by two invited contributions on new topics rooted in recent developments of linear logic. The book derives from a summer school that was the climax of the EU Training and Mobility of Researchers project 'Linear Logic in Computer Science'. It is an excellent introduction to some of the most active research topics in the area. (shrink)

The familiar connective of negation is broken into two operations: linear negation which is the purely negative part of negation and the modality “of course” which has the meaning of a reaffirmation. Following this basic discovery, a completely new approach to the whole area between constructive logics and programmation is initiated.

This work deals with the exponential fragment of Girard's linear logic without the contraction rule, a logical system which has a natural relation with the direct logic . A new sequent calculus for this logic is presented in order to remove the weakening rule and recover its behavior via a special treatment of the propositional constants, so that the process of cut-elimination can be performed using only “local” reductions. Hence a typed calculus, which admits only local (...) rewriting rules, can be introduced in a natural manner. Its main properties — normalizability and confluence — has been investigated; moreover this calculus has been proved to satisfy a Curry-Howard isomorphism with respect to the logical system in question. MSC: 03B40, 03F05. (shrink)

Just as intuitionistic proofs can be modeled by functions, linear logic proofs, being symmetric in the inputs and outputs, can be modeled by relations . However generic relations do not establish any functional dependence between the arguments, and therefore it is questionable whether they can be thought as reasonable generalizations of functions. On the other hand, in some situations one can speak in some precise sense about an implicit functional dependence defined by a relation. It turns out that (...) it is possible to model linear logic with implicit functions rather than general relations, an adequate language for such a semantics being differential calculus. This results in a non-degenerate model enjoying quite strong completeness properties. (shrink)

We consider finite multisets over some set of urelements equipped only with additive union [uplus ] and show that the {[otimes], -0}-Horn fragment of Intuitionistic Linear Logic has a sound and complete interpretation in them by interpreting [otimes] as [uplus ]. The linear implication is interpreted by ordered pairs of multisets expressing replacement. The operator ! is also defined in an asymptotic way. Soundness, completeness and partial completeness results are proved for the {×, -0, !}-Horn fragment as (...) well. (shrink)

Levesque et al. have defined a programming language, Golog, in order to reason about complex actions within the framework of the situation calculus. We build on previous work of ours and show how to translate Golog into linear logic, suitably augmented.

A new characterization of all the MV-algebras embedded in a CL-algebra has been presented. A new sequent calculus for Lukasiewicz ℵ0-valued logic is introduced. Some links between this calculus and the sequent calculus for multiplicative additive linear logic are established. It has been shown that Lukasiewicz ℵ0-valued logic can be embedded in a suitable extension of MALL.

In an unpublished note Reddy introduced an extended intuitionistic linear calculus, called LLMS (for Linear Logic Model of State), to model state manipulation via the notions of sequential composition and ‘regenerative values’. His calculus introduces the connective ‘before’ ▹ and an associated modality †, for the storage of objects sequentially reusable. Earlier and independently de Paiva introduced a (collection of) dialectica categorical models for (classical and intuitionistic) Linear Logic, the categories Dial2Set. These categories contain, apart (...) from the structure needed to model linear logic, an extra tensor product functor and an extra comonad structure corresponding to a modality related to the extra tensor product. It is surprising that these works arising from completely different motivations can be related in a meaningful way. In this article, following joint work with Corrêa and Haeusler, we first adapt Reddy's system LLMS providing a commutative version of the connective ‘before’ and its associated modality and then construct a dialectica category on Sets , which we show is a sound model for the modified version of Reddy's the system LLMSc. Moreover, following the work of Tucker, we provide another variant of the Dialectica categories with a non-commutative tensor and its associated modality, which models soundlyLLMS itself. We conclude with some speculation on future applications. (shrink)

In this paper we introduce a new type of nets with bounded types of distributed resources . Linear Logic to describe the behaviour of BR-nets is defined. It is based on Girard's Linear Logic but captures not only consumption of resources but their presence as well. Theorem of soundness and completeness of the proposed axiomatization is proved and the complexity of the provability problem is established for the general case and some particular ones.

The introduction of Linear Logic extends the Curry-Howard Isomorphism to intensional aspects of the typed functional programming. In particular, every formula of Linear Logic tells whether the term it is a type for, can be either erased/duplicated or not, during a computation. So, Linear Logic can be seen as a model of a computational environment with an explicit control about the management of resources.This paper introduces a typed functional language Λ! and a categorical model (...) for it.The terms of Λ! encode a version of natural deduction for Intuitionistic Linear Logic such that linear and non linear assumptions are managed multiplicatively and additively, respectively. Correspondingly, the terms of Λ! are built out of two disjoint sets of variables. Moreover, the λ-abstractions of Λ! bind variables and patterns. The use of two different kinds of variables and the patterns allow a very compact definition of the one-step operational semantics of Λ!, unlike all other extensions of Curry-Howard Isomorphism to Intuitionistic Linear Logic. The language Λ! is Church-Rosser and enjoys both Strong Normalizability and Subject Reduction.The categorical model induces operational equivalences like, for example, a set of extensional equivalences.The paper presents also an untyped version of Λ! and a type assignment for it, using formulas of Linear Logic as types. The type assignment inherits from Λ! all the good computational properties and enjoys also the Principal-Type Property. (shrink)

In this paper the questions remaining open about NP-completeness of multiplicative and Horn fragments of the Linear Logic and the Linear Logic with the weakening rule are answered.

In this paper we investigate two logics (and their fragments) from an algebraic point of view. The two logics are: $$\textsf{MALL}$$ (multiplicative-additive Linear Logic) and $$\textsf{LL}$$ (classical Linear Logic). Both logics turn out to be strongly algebraizable in the sense of Blok and Pigozzi and their equivalent algebraic semantics are, respectively, the variety of Girard algebras and the variety of girales. We show that any variety of girales has a TD-term and hence equationally definable principal congruences. (...) Also we investigate the structure of the algebras in question, thus obtaining a representation theorem for Girard algebras and girales. We also prove that congruence lattices of girales are really congruence lattices of Heyting algebras, thus determining the simple and subdirectly irreducible girales. Finally we introduce a class of examples showing that the variety of girales contains infinitely many nonisomorphic finite simple algebras. (shrink)

We show that linear logic can serve as an expressive framework in which to model a rich variety of combinatorial auction mechanisms. Due to its resource-sensitive nature, linear logic can easily represent bids in combinatorial auctions in which goods may be sold in multiple units, and we show how it naturally generalises several bidding languages familiar from the literature. Moreover, the winner determination problem, i.e., the problem of computing an allocation of goods to bidders producing a (...) certain amount of revenue for the auctioneer, can be modelled as the problem of finding a proof for a particular linear logic sequent. (shrink)

A new logic, quantized intuitionistic linear logic, is introduced, and is closely related to the logic which corresponds to Mulvey and Pelletier's involutive quantales. Some cut-free sequent calculi with a new property quantization principle and some complete semantics such as an involutive quantale model and a quantale model are obtained for QILL. The relationship between QILL and Wansing's extended intuitionistic linear logic with strong negation is also observed using such syntactical and semantical frameworks.

We present a reading of the traditional syllogistics in a fragment of the propositional intuitionistic multiplicative linear logic and prove that with respect to a diagrammatic logical calculus that we introduced in a previous paper, a syllogism is provable in such a fragment if and only if it is diagrammatically provable. We extend this result to syllogistics with complemented terms à la De Morgan, with respect to a suitable extension of the diagrammatic reasoning system for the traditional case (...) and a corresponding reading of such De Morgan style syllogistics in the previously referred to fragment of linear logic. (shrink)

In this paper we give a brief treatment of a theory of proofs for a system of Full Intuitionistic Linear Logic. This system is distinct from Classical Linear Logic, but unlike the standard Intuitionistic Linear Logic of Girard and Lafont includes the multiplicative disjunction par. This connective does have an entirely natural interpretation in a variety of categorical models of Intuitionistic Linear Logic. The main proof-theoretic problem arises from the observation of Schellinx (...) that cut elimination fails outright for an intuitive formulation of Full Intuitionistic Linear Logic; the nub of the problem is the interaction between par and linear implication. We present here a term assignment system which gives an interpretation of proofs as some kind of non-deterministic function. In this way we find a system which does enjoy cut elimination. The system is a direct result of an analysis of the categorical semantics, though we make an effort to present the system as if it were purely a proof-theoretic construction. (shrink)

We show how to embed a framework for multilateral negotiation, in which a group of agents implement a sequence of deals concerning the exchange of a number of resources, into linear logic. In this model, multisets of goods, allocations of resources, preferences of agents, and deals are all modelled as formulas of linear logic. Whether or not a proposed deal is rational, given the preferences of the agents concerned, reduces to a question of provability, as does (...) the question of whether there exists a sequence of deals leading to an allocation with certain desirable properties, such as maximising social welfare. Thus, linear logic provides a formal basis for modelling convergence properties in distributed resource allocation. (shrink)

We describe how Intuitionistic Linear Logic can be used to provide a unified logical account for agents to find and execute plans. This account supports the modelling of agent interaction, including dialogue; allows agents to be robust to unexpected events and failures; and supports significant reuse of agent specifications. The framework has been implemented and several case studies have been considered. Further applications include human–computer interfaces as well as agent interaction in the semantic web.

The introduction of Linear Logic extends the Curry-Howard Isomorphism to intensional aspects of the typed functional programming. In particular, every formula of Linear Logic tells whether the term it is a type for, can be either erased/duplicated or not, during a computation. So, Linear Logic can be seen as a model of a computational environment with an explicit control about the management of resources.

§ 1. Introduction. Perhaps the most surprising recent development in complexity theory is the discovery that the class NP can be characterized using a form of randomized proof checker that only examines a constant number of bits of the “proof” that a string is in a language [6, 5, 31, 3, 4]. More specifically, writing ∣x∣ for the length of a string x, a language L in the class NP of languages recognizable in Nondeterministic polynomial time is traditionally given by (...) a polynomial p and a polynomial-time predicate P such that a string x is in L iff there is some string y satisfying P, where ∣y∣ ≤ p. Intuitively, we can think of a string y as a possible proof that x ϵ L, with the predicate P some kind of proof checker that distinguishes good proofs from bad ones. A string x is therefore in a language L ϵ NP if there is a short proof that x ϵ L, and not in L otherwise. The surprising discovery is that the deterministic proof checker that reads the entire input and proof can be replaced by a probabilistic verifier that on input x and possible proof y, where y is presented in a certain way, flips at most O coins and reads at most a constant number of bits of x and y. Obviously, a probabilistic verifier that does not read the whole proof will sometimes make mistakes. However, the surprising and essentially non-intuitive mathematical fact is that for each language L in NP, it is possible to find a polynomial q and verifier V flipping a logarithmic number of coins and reading a constant number of bits such that, for any x ϵ L, there exists y with ∣y∣ ≤ q and with V accepting with probability 1 and, for x ∉ L, there is no y with ∣y∣ ≤ q and with V accepting with probability ≥ 1/4. This idea canalsobeextended to PSPACE [10, 9], using a game that alternates between two players instead of a proof presented by a “single player.”. (shrink)

A Linear Logic automaton is a hybrid of a finite automaton and a non-deterministic Petri net. LL automata commands are represented by propositional Horn Linear Logic formulas. Computations performed by LL automata directly correspond to cut-free derivations in Linear Logic.A programming language of LL automata is developed in which typical sequential, non-deterministic and parallel programming constructs are expressed in the natural way.All non-deterministic computations, e.g. computations performed by programs built up of guarded commands in (...) the Dijkstra's approach to non-deterministic programming, are directly simulated within the framework of Linear Logic automata, and thereby within the Horn framework of Linear Logic. (shrink)

Linear logic, introduced in 1986 by J.-Y. Girard, is based upon a fine grain analysis of the main proof-theoretical notions of logic. The subject develops along the lines of denotational semantics, proof nets and the geometry of interaction. Its basic dynamical nature has attracted computer scientists, and various promising connections have been made in the areas of optimal program execution, interaction nets and knowledge representation. This book is the refereed proceedings of the first international meeting on (...) class='Hi'>linear logic held at Cornell University, in June 1993. Survey papers devoted to specific areas of linear logic, as well as an extensive general introduction to the subject by J.-Y. Girard, have been added, so as to make this book a valuable tool both for the beginner and for the advanced researcher. (shrink)

The question at issue is to develop a computational interpretation of Linear Logic [8] and to establish exactly its expressive power. We follow the bottom-up approach. This involves starting with the simplest of the systems we are interested in, and then expanding them step-by-step. We begin with the !-Horn fragment of Linear Logic, which uses only positive literals, the linear implication ⊸, the tensor product ⊗, and the modal storage operator !. We give a complete (...) computational interpretation for the !-Horn fragment of Linear Logic and for some natural generalizations of it formed by introducing additive connectives. Here we use the well-known ‘ or ’-like connective ⊕, and, for the sake of the computational duality, we introduce a new ‘ and ’-like connective @ For !-Horn sequents, we prove that their derivability problem is directly equivalent to the reachability problem for Petri nets, which is known to be decidable [19]. For the -Horn fragment of Linear Logic, which uses only positive literals, the linear implication ⊸, the tensor product ⊗, the modal storage operator!, and the additive ‘disjunction’ ⊕, we prove that standard Minsky machines [21] can be directly encoded in this -Horn fragment. Standard Minsky machines can be directly encoded in the corresponding ‘dual’ -Horn fragment of Linear Logic, as well. As a corollary, both these fragments of Linear Logic are proved to be undecidable. (shrink)

Linear logic, introduced by Girard, is a refinement of classical logic with a natural, intrinsic accounting of resources. This accounting is made possible by removing the ‘structural’ rules of contraction and weakening, adding a modal operator and adding finer versions of the propositional connectives. Linear logic has fundamental logical interest and applications to computer science, particularly to Petri nets, concurrency, storage allocation, garbage collection and the control structure of logic programs. In addition, there is (...) a direct correspondence between polynomial-time computation and proof normalization in a bounded form of linear logic. In this paper we show that unlike most other propositional logics, full propositional linear logic is undecidable. Further, we prove that without the modal storage operator, which indicates unboundedness of resources, the decision problem becomes PSPACE-complete. We also establish membership in NP for the multiplicative fragment, NP-completeness for the multiplicative fragment extended with unrestricted weakening, and undecidability for fragments of noncommutative propositional linear logic. (shrink)

In this paper we 1. provide a natural deduction system for full first-order linear logic, 2. introduce Curry-Howard-style terms for this version of linear logic, 3. extend the notion of substitution of Curry-Howard terms for term variables, 4. define the reduction rules for the Curry-Howard terms and 5. outline a proof of the strong normalization for the full system of linear logic using a development of Girard's candidates for reducibility, thereby providing an alternative to (...) Girard's proof using proof-nets. (shrink)

Linear Logic is a versatile framework with diverse applications in computer science and mathematics. One intriguing fragment of Linear Logic is Multiplicative-Additive Linear Logic (MALL), which forms the exponential-free component of the larger framework. Modifying MALL, researchers have explored weaker logics such as Noncommutative MALL (Bilinear Logic, BL) and Cyclic MALL (CyMALL) to investigate variations in commutativity. In this paper, we focus on Cyclic Nonassociative Bilinear Logic (CyNBL), a variant that combines noncommutativity (...) and nonassociativity. We introduce a sequent system for CyNBL, which includes an auxiliary system for incorporating nonlogical axioms. Notably, we establish the cut elimination property for CyNBL. Moreover, we establish the strong conservativeness of CyNBL over Full Nonassociative Lambek Calculus (FNL) without additive constants. The paper highlights that all proofs are constructed using syntactic methods, ensuring their constructive nature. We provide insights into constructing cut-free proofs and establishing a logical relationship between CyNBL and FNL. (shrink)

We introduce an extended intuitionistic linear logic with strong negation and modality. The logic presented is a modal extension of Wansing's extended linear logic with strong negation. First, we propose three types of cut-free sequent calculi for this new logic. The first one is named a subformula calculus, which yields the subformula property. The second one is termed a dual calculus, which has positive and negative sequents. The third one is called a triple-context calculus, (...) which is regarded as a natural extension or generalization of Hodas and Miller's dual-context calculus appearing in a linear logic programming language. Second, we present a concurrent process calculus based on the logic. This calculus is an extension of Okada's process calculus. Third, we introduce a Kripke type semantics for a fragment of the logic, and show the completeness theorems with respect to the semantics. Finally, we mention a logic programming language based on the triple-context calculus. (shrink)

In this paper we continue the study of Girard's Linear Logic and introduce a new Linear Logic with modalities. Our logic describes not only the consumption, but also the presence of resources. We introduce a new semantics and a new calculus for this logic. In contrast to the results of Lincoln [7] and Kanovich [4] about the NP-completeness of the problem of the construction of a proof for a given sequent in the multiplicative fragment (...) of Girard's Linear Logic, we present here a non-exponential algorithm to construct a proof for a given sequent and a given point of a given model in our Linear Logic. (shrink)

, from Stanford Encyclopaedia of Philosophy.

We present a Kripke model for Girard's Linear Logic (without exponentials) in a conservative fashion where the logical functors beyond the basic lattice operations may be added one by one without recourse to such things as negation. You can either have some logical functors or not as you choose. Commutatively and associatively are isolated in such a way that the base Kripke model is a model for noncommutative, nonassociative Linear Logic. We also extend the logic (...) by adding a coimplication operator, similar to Curry's subtraction operator, which is resituated with Linear Logic's contensor product. And we can add contraction to get nondistributive Relevance Logic. The model rests heavily on Urquhart's representation of nondistributive lattices and also on Dunn's Gaggle Theory. Indeed, the paper may be viewed as an investigation into nondistributive Gaggle Theory restricted to binary operations. The valuations on the Kripke model are three valued: true, false, and indifferent. The lattice representation theorem of Urquhart has the nice feature of yielding Priestley's representation theorem for distributive lattices if the original lattice happens to be distributive. Hence the representation is consistent with Stone's representation of distributive and Boolean lattices, and our semantics is consistent with the Lemmon-Scott representation of modal algebras and the Routley-Meyer semantics for Relevance Logic. (shrink)

The starting point of the present study is the interpretation of intuitionistic linear logic in Petri nets proposed by U. Engberg and G. Winskel. We show that several categories of order algebras provide equivalent interpretations of this logic, and identify the category of the so called strongly coherent quantales arising in these interpretations. The equivalence of the interpretations is intimately related to the categorical facts that the aforementioned categories are connected with each other via adjunctions, and the (...) compositions of the connecting functors with co-domain the category of strongly coherent quantales are dense. In particular, each quantale canonically induces a Petri net, and this association gives rise to an adjunction between the category of quantales and a category whose objects are all Petri nets. (shrink)

We consider a class of graphs embedded in $R^2$ as noncommutative proof-nets with an explicit exchange rule. We give two characterization of such proof-nets, one representing proof-nets as CW-complexes in a two-dimensional disc, the other extending a characterization by Asperti. As a corollary, we obtain that the test of correctness in the case of planar graphs is linear in the size of the data. Braided proof-nets are proof-nets for multiplicative linear logic with Mix embedded in $R^3$ . (...) In order to prove the cut-elimination theorem, we consider proof-nets in $R^2$ as projections of braided proof-nets under regular isotopy. (shrink)

We present a game semantics in the style of Lorenzen for Girard's linear logic . Lorenzen suggested that the meaning of a proposition should be specified by telling how to conduct a debate between a proponent P who asserts and an opponent O who denies . Thus propositions are interpreted as games, connectives as operations on games, and validity as existence of a winning strategy for P. We propose that the connectives of linear logic can be (...) naturally interpreted as the operations on games introduced for entirely different purposes by Blass . We show that affine logic, i.e., linear logic plus the rule of weakening, is sound for this interpretation. We also obtain a completeness theorem for the additive fragment of affine logic, but we show that completeness fails for the multiplicative fragment. On the other hand, for the multiplicative fragment, we obtain a simple characterization of game-semantical validity in terms of classical tautologies. An analysis of the failure of completeness for the multiplicative fragment leads to the conclusion that the game interpretation of the connective is weaker than the interpretation implicit in Girard's proof rules; we discuss the differences between the two interpretations and their relative advantages and disadvantages. Finally, we discuss how Gödel's Dialectica interpretation , which was connected to linear logic by de Paiva , fits with game semantics. (shrink)

Proof-theoretic semantics (P-tS) is an innovative approach to grounding logical meaning in terms of proofs rather than traditional truth-conditional semantics. The point is not that one provides a proof system, but rather that one articulates meaning in terms of proofs and provability. To elucidate this paradigm shift, we commence with an introduction that contrasts the fundamental tenets of P-tS with the more prevalent model-theoretic approach to semantics. The contribution of this paper is a P-tS for a substructural logic, intuitionistic (...) multiplicative linear logic (IMLL). Specifically, we meticulously examine and refine the established P-tS for intuitionistic propositional logic. Subsequently, we present two novel and comprehensive forms of P-tS for IMLL. Notably, the semantics for IMLL in this paper embodies its resource interpretation through its number-of-uses reading (restricted to atoms). This stands in contrast to the conventional model-theoretic semantics of the logic, underscoring the value that P-tS brings to substructural logics. (shrink)

This short note considers the formulation of Full Intuitionistic Linear Logic given by Hyland and de Paiva . Unfortunately the formulation is not closed under the process of cut elimination. This note proposes an alternative formulation based on the notion of patterns.