Abstract The proof theory and semantics of intuitionistic modal logics have been studied by Simpson in terms of Prawitz-style labelled natural deduction systems and Kripke models. An alternative to model-theoretic semantics is provided by proof-theoretic semantics, which is a logical realization of inferentialism, in which the meaning of constructs is understood through their use. The key idea in proof-theoretic semantics is that of a base of atomic rules, all of which refer only to propositional atoms and involve no logical connectives. A specific form of proof-theoretic semantics, known as base-extension semantics (B-eS), is concerned with the validity of formulae and provides a direct counterpart to Kripke models that is grounded in the provability of atomic formulae in a base. We establish, systematically, B-eS for Simpson’s intuitionistic modal logics and, also systematically, obtain soundness and completeness theorems with respect to Simpson’s natural deduction systems.

Abstract We present a comprehensive programme analysing the decomposition of proof systems for non-classical logics into proof systems for other logics, especially classical logic, using an algebra of constraints. That is, one recovers a proof system for a target logic by enriching a proof system for another, typically simpler, logic with an algebra of constraints that act as correctness conditions on the latter to capture the former; e.g. one may use Boolean algebra to give constraints in a sequent calculus for classical propositional logic to produce a sequent calculus for intuitionistic propositional logic. The idea behind such forms of decomposition is to obtain a tool for uniform and modular treatment of proof theory and to provide a bridge between semantics logics and their proof theory. The paper discusses the theoretical background of the project and provides several illustrations of its work in the field of intuitionistic and modal logics: including, a uniform treatment of modular and cut-free proof systems for a large class of propositional logics; a general criterion for a novel approach to soundness and completeness of a logic with respect to a model-theoretic semantics; and a case study deriving a model-theoretic semantics from a proof-theoretic specification of a logic.

Abstract This work is the first exploration of proof-theoretic semantics for a substructural logic. It focuses on the base-extension semantics (B-eS) for intuitionistic multiplicative linear logic ( $$\mathrm IMLL$$ ). The starting point is a review of Sandqvist’s B-eS for intuitionistic propositional logic (IPL), for which we propose an alternative treatment of conjunction that takes the form of thegeneralizedelimination rule for the connective. The resulting semantics is shown to be sound and complete. This motivates our main contribution, a B-eS for $$\mathrm IMLL$$ , in which the definitions of the logical constants all take the form of their elimination rule and for which soundness and completeness are established.

Security policy-makers (influencers) in an organization set security policies that embody intended behaviours for employees (as decision-makers) to follow. Decision-makers then face choices, where this is not simply a binary decision of whether to comply or not, but also how to approach compliance and secure working alongside other workplace pressures, and limited resources for identifying optimal security-related choices. Conflict arises because of information asymmetries present in the relationship, where influencers and decision-makers both consider costs, gains, and losses in ways which are not necessarily aligned. With the need to promote ‘good enough’ decisions about security-related behaviours under such constraints, we hypothesize that actions to resolve this misalignment can benefit from constructs from both traditional economics and behavioural economics. Here we demonstrate how current approaches to security behaviour provisioning in organizations mirror rational-agent economics, even where behavioural economics is embodied in the promotion of individual security behaviours. We develop and present a framework to accommodate bounded security decision-making, within an ongoing programme of behaviours which must be provisioned for and supported. Our four stage plan to Capture, Adapt, Realign, and Enable behaviour choices provides guidance for security managers, focusing on a more effective response to the uncertainty associated with security behaviour in organizations.

Concurrent Kleene Algebra is an elegant tool for equational reasoning about concurrent programs. An important feature of concurrent programs that is missing from CKA is the ability to restrict legal interleavings. To remedy this we extend the standard model of CKA, namely pomsets, with a new feature, called boxes, which can specify that part of the system is protected from outside interference. We study the algebraic properties of this new model. Another drawback of CKA is that the language used for expressing properties of programs is the same as that which is used to express programs themselves. This is often too restrictive for practical purposes. We provide a logic, "pomset logic", that is an assertion language for specifying such properties, and which is interpreted on pomsets with boxes. In contrast with other approaches, this logic is not state-based, but rather characterizes the runtime behaviour of a program. We develop the basic metatheory for the relationship between pomset logic and CKA, including frame rules to support local reasoning, and illustrate this relationship with simple examples.

Abstract We present a substructural epistemic logic, based on Boolean BI, in which the epistemic modalities are parametrized on agents’ local resources. The new modalities can be seen as generalizations of the usual epistemic modalities. The logic combines Boolean BI’s resource semantics—we introduce BI and its resource semantics at some length—with epistemic agency. We illustrate the use of the logic in systems modelling by discussing some examples about access control, including semaphores, using resource tokens. We also give a labelled tableaux calculus and establish soundness and completeness with respect to the resource semantics.

In recent years, the key principles behind Separation Logic have been generalized to generate formalisms for a number of verification tasks in program analysis via the formulation of ‘non-standard’ models utilizing notions of separation distinct from heap disjointness. These models can typically be characterized by a separation theory , a collection of first-order axioms in the signature of the model’s underlying ordered monoid. While all separation theories are interpreted by models that instantiate a common mathematical structure, many are undefinable in Separation Logic and determine different classes of valid formulae, leading to incompleteness for existing proof systems. Generalizing systems utilized in the proof theory of bunched logics, we propose a framework of tableaux calculi that are generically extendable by rules that correspond to separation theories axiomatized by coherent formulas. This class covers all separation theories in the literature—for both classical and intuitionistic Separation Logic—as well as axioms for a number of related formalisms appropriate for reasoning about complex systems, security, and concurrency. Parametric soundness and completeness of the framework is proved by a novel representation of tableaux systems as coherent theories, suggesting a strategy for implementation and a tentative first step towards a new logical framework for non-classical logics.

Models of complex systems are widely used in the physical and social sciences, and the concept of layering, typically building upon graph-theoretic structure, is a common feature. We describe an intuitionistic substructural logic called ILGL that gives an account of layering. The logic is a bunched system, combining the usual intuitionistic connectives, together with a non-commutative, non-associative conjunction (used to capture layering) and its associated implications. We give soundness and completeness theorems for a labelled tableaux system with respect to a Kripke semantics on graphs. We then give an equivalent relational semantics, itself proven equivalent to an algebraic semantics via a representation theorem. We utilise this result in two ways. First, we prove decidability of the logic by showing the finite embeddability property holds for the algebraic semantics. Second, we prove a Stone-type duality theorem for the logic. By introducing the notions of ILGL hyperdoctrine and indexed layered frame we are able to extend this result to a predicate version of the logic and prove soundness and completeness theorems for an extension of the layered graph semantics . We indicate the utility of predicate ILGL with a resource-labelled bigraph model.

Understanding the boundaries of trust is a key aspect of accurately modelling the structure and behaviour of multi-agent systems with heterogeneous motivating factors. Reasoning about these boundaries in highly interconnected, information-rich ecosystems is complex, and dependent upon modelling at the correct level of abstraction. Building on an established mathematical systems modelling framework that captures the classical view of distributed systems, we develop a modelling framework that incorporates both logical and cost-based descriptions of systems, which allows us to establish a definition of an agent's trust domain based on the satisfaction of logical properties at acceptable utility (handled here simply as cost) to the agent, of verification. In addition to the technical properties of the modelling framework itself, we establish a theory of logical combinators, including substitution, for composing trust domains to form relatively complex models of trust. We illustrate the ideas with examples throughout.

Logics for Resources, Processes, and Programs (LRPP) is an occasional series of international workshops which aims to explore the current state of logical and semantic approaches to reasoning about the programs that implement the processes that manipulate system resources in order to deliver services. LRPP is concerned with ideas that range from purely logical and semantic work that bears upon the foundations of system modelling through to implemented tools that support formal reasoning about programs and systems. This Special Issue of the Journal of Logic and Computation comprises a selection of papers inspired by the 2013 LRPP workshop, held in association with the Tableaux 2013 conference in Nancy, France and submitted from an open call for papers following the workshop. There are six papers in this special issue, mostly concerned with theoretical logical and semantic aspects of concepts that are of significance in systems of interacting agents. The paper by Nguyen, Alechina, Logan and Rakib, entitled ‘Resource-bounded alternating time temporal logic’, is concerned with reasoning about coalitional ability. As there is no straightforward way of reasoning about resource requirements in logics such as Coalition Logic (CL) and Alternating-time Temporal Logic (ATL), the authors define a logic for reasoning about coalitional ability under resource constraints. They extend ATL with costs of actions and hence of strategies, and give a complete and sound axiomatization of the resulting logic, Resource-Bounded ATL (RB-ATL), and a model-checking algorithm for it.

Models of complex systems are widely used in the physical and social sciences, and the concept of layering, typically building upon graph-theoretic structure, is a common feature. We describe an intuitionistic substructural logic that gives an account of layering. As in other bunched systems, the logic includes the usual intuitionistic connectives, together with a non-commutative, non-associative conjunction (used to capture layering) and its associated implications. We give a soundness and completeness theorem for a labelled tableaux system with respect to a Kripke semantics on graphs. To demonstrate the utility of the logic, we show how to represent systems and security examples, illuminating the relationship between services/policies and the infrastructures/architectures to which they are applied.

Our goal is to refocus the question about cybersecurity research from 'is this process scientific' to 'why is this scientific process producing unsatisfactory results'. We focus on five common complaints that claim cybersecurity is not or cannot be scientific. Many of these complaints presume views associated with the philosophical school known as Logical Empiricism that more recent scholarship has largely modified or rejected. Modern philosophy of science, supported by mathematical modeling methods, provides constructive resources to mitigate all purported challenges to a science of security. Therefore, we argue the community currently practices a science of cybersecurity. A philosophy of science perspective suggests the following form of practice: structured observation to seek intelligible explanations of phenomena, evaluating explanations in many ways, with specialized fields (including engineering and forensics) constraining explanations within their own expertise, inter-translating where necessary. A natural question to pursue in future work is how collecting, evaluating, and analyzing evidence for such explanations is different in security than other sciences.

Abstract We introduce a substructural modal logic of utility that can be used to reason aboutoptimality with respect to properties of states. Our notion of state is quite general, and is able to represent resource allocation problems in distributed systems. The underlying logic is a variant of the modal logic of bunched implications, and based on resource semantics, which is closely related to concurrent separation logic. We consider a labelled transition semantics and establish conditions under which Hennessy—Milner soundness and completeness hold. By considering notions of cost, strategy and utility, we are able to formulate characterizations of Pareto optimality, best responses, and Nash equilibrium within resource semantics. We also show that our logic is able to serve as a logic for a fully featured process algebra and explain the interaction between utility and the structure of processes.

Proposition 6.2 (2) and (3) of ‘A substructural logic for layered graphs’, by M. Collinson, K. McDonald, and D. Pym, Journal of Logic and Computation (2014) 24 (4): 953-988, are incorrect. We provide explanations of the failures of the intended proofs and specific counterexamples. The article makes no further use of the claims and there are no consequences for the theory or examples that are presented.

We describe a uniform logical framework, based on a bunched logic that combines classical additives and very weak multiplicatives, for reasoning compositionally about access control policy models. We show how our approach takes account of the underlying system architecture, and so provides a way to identify and reason about how vulnerabilities may arise (and be removed) as a result of the architecture of the system. We consider, using frame rules, how local properties of access control policies are maintained as the system architecture evolves.

Mathematical modelling and simulation modelling are fundamental tools of engineering, science, and social sciences such as economics, and provide decision-support tools in management. Mathematical models are essentially deployed at all scales, all levels of complexity, and all levels of abstraction. Models are often required to be executable, as a simulation, on a computer. We present some contributions to the process-theoretic and logical foundations of discrete-event modelling with resources and processes. Building on previous work in resource semantics, process calculus, and modal logic, we describe a process calculus with an explicit representation of resources in which processes and resources co-evolve. The calculus is closely connected to a substructural modal logic that may be used as a specification language for properties of models. In contrast to earlier work, we formulate the resource semantics, and its relationship with process calculus, in such a way that we obtain soundness and completeness of bisimulation with respect to logical equivalence for the naturally full range of logical connectives and modalities. We give a range of examples of the use of the process combinators and logical structure to describe system structure and behaviour.

We present a logic of separating modalities, LSM, that is based on Boolean BI. LSM's modalities, which generalize those of S4, combine, within a quite general relational semantics, BI's resource semantics with modal accessibility. We provide a range of examples illustrating their use for modelling. We give a proof system based on a labelled tableaux calculus with countermodel extraction, establishing its soundness and completeness with respect to the semantics.

Complex systems, be they natural or synthetic, are ubiquitous. In particular, complex networks of devices and services underpin most of society's operations. By their very nature, such systems are difficult to conceptualize and reason about effectively. The concept of layering is widespread in complex systems, but has not been considered conceptually. Noting that graphs are a key formalism in the description of complex systems, we establish a notion of a layered graph. We provide a logical characterization of this notion of layering using a non-associative, non-commutative substructural, separating logic. We provide soundness and completeness results for a class of algebraic models that includes layered graphs, which give a mathematically substantial semantics to this very weak logic. We explain, via examples, applications in information processing and security.

The matrix method, due to Bibel and Andrews, is a proof procedure designed for automated theorem-proving. We show that underlying this method is a fully structured combinatorial model of conventional classical proof theory.

Managing information security in the cloud is a challenge. Traditional checklist approaches to standards compliance may well provide compliance, but do not guarantee to provide security assurance. The complexity of cloud relationships must be acknowledged and explicitly managed by recognising the implications of self-interest of each party involved. We begin development of a conceptual modelling framework for cloud security assurance that can be used as a starting point for effective continuous security assurance, together with a high level of compliance.

We discuss the concept of information stewardship in cloud-based business ecosystems. The constituent concepts of stewardship -- which we believe will be crucial to the successful development of cloud-based business of all kinds -- extend those of security to encompass concepts of objectives, ethics/values, sustainability, and resilience: all familiar from the stewardship of natural resources. Our view is based on rigorous approaches from mathematical systems modelling and economics, and is informed by concepts from natural resource management and information assurance.

Abstract The access control problem in computer security is fundamentally concerned with the ability of system entities to see, make use of, or alter various system resources. We provide a mathematical framework for modelling and reasoning about (distributed) systems with access control. This is based on a calculus of resources and processes together with a Hennessy–Milner-style modal logic, based on the connectives of bunched logic, for which an appropriate correspondence theorem obtains. As a consequence we get a consistent account of both operational behaviour and logical reasoning for systems with access control features. In particular, we are able to introduce a process combinator that describes, as a form of concurrent composition, the action of one agent in the role of another, and provide a logical characterization of this operator via a modality ‘says’. We give a range of examples, including analyses of co-signing, roles, and chains of trust, which illustrates the utility of our mathematical framework.

No abstract available.

Experience of practical systems modelling suggests that the key conceptual components of a model of a system are processes, resources, locations, and environment. In recent work, we have given a process-theoretic account of this view in which resources as well as processes are first-class citizens. This process calculus, SCRP, captures the structural aspects of the semantics of the Demos2k modelling tool. Demos2k represents environment stochastically using a wide range of probability distributions and queue-like data structures. Associated with SCRP is a (bunched) modal logic, MBI, which combines the usual additive connectives of Hennessy-Milner logic with their multiplicative counterparts. In this paper, we complete our conceptual framework by adding to SCRP and MBI an account of a notion of location that is simple, yet sufficiently expressive to capture naturally a wide range of forms of location, both spatial and logical. We also provide a description of an extension of the Demos2k tool to incorporate this notion of location. 1

Mathematical modelling is one of the fundamental tools of science and engineering. Very often, models are required to be executable, as a simulation, on a computer. In this paper, we present some contributions to the process-theoretic and logical foundations of discrete-event modelling with resources and processes. We present a process calculus with an explicit representation of resources in which processes and resources co-evolve. The calculus is closely connected to a logic that may be used as a specification language for properties of models. The logic is strong enough to allow requirements that a system has a certain structure: for example, that it is a parallel composite of subsystems. This work consolidates, extends and improves upon aspects of earlier work of ours in this area. An extended example, consisting of a semantics for a simple parallel programming language, indicates a connection with separating logics for concurrency.

We describe a polymorphic, typed lambda calculus with substructural features. This calculus extends the first-order substructural lambda calculus αλ associated with bunched logic. A particular novelty of our new calculus is the substructural treatment of second-order variables. This is accomplished through the use of bunches of type variables in typing contexts. Both additive and multiplicative forms of polymorphic abstraction are then supported. The calculus has sensible proof-theoretic properties and a straightforward categorical semantics using indexed categories. We produce a model for additive polymorphism with first-order bunching based on partial equivalence relations. We consider additive and multiplicative existential quantifiers separately from the universal quantifiers.

We present a correction for an error that occurs in the following paper Formal Aspects of Computing (2006) 18:495-517.At first sight, the error appears to be simply a misplaced quantifier in the definition of bisimulation.We explain, however, that the error and its correction reveal a subtle interaction between the substructural connectives of MBI and the resource-process calculus SCRP.We begin with a specific example which illustrates the error.We include also the known typographical errors.We include also a statement of the consequences of these errata for the paper Electronic Notes in Theoretical Computer Science 172, 545-587, 2007, which builds directly upon Formal Aspects of Computing (2006) 18:495-517 and which illustrates the significance of these errata.

It is well known that weakening and contraction cause naive categorical models of the classical sequent calculus to collapse to Boolean lattices. In previous work, summarised briefly herein, we have provided a class of models called classical categories that is sound and complete and avoids this collapse by interpreting cut reduction by a poset enrichment. Examples of classical categories include boolean lattices and the category of sets and relations, where both conjunction and disjunction are modelled by the set-theoretic product. In this article, which is self-contained, we present an improved axiomatisation of classical categories, together with a deep exploration of their structural theory. Observing that the collapse already happens in the absence of negation, we start with negation-free models called Dummett categories . Examples of these include, besides the classical categories mentioned above, the category of sets and relations, where both conjunction and disjunction are modelled by the disjoint union. We prove that Dummett categories are MIX, and that the partial order can be derived from hom-semilattices, which have a straightforward proof-theoretic definition. Moreover, we show that the Geometry-of-Interaction construction can be extended from multiplicative linear logic to classical logic by applying it to obtain a classical category from a Dummett category. Along the way, we gain detailed insights into the changes that proofs undergo during cut elimination in the presence of weakening and contraction.

Abstract Recent advances in logics for reasoning about resources provide a new approach to compositional reasoning in interacting systems. We present a calculus of resources and processes, based on a development of Milner’s synchronous calculus of communication systems, SCCS, that uses an explicit model of resource. Our calculus models the co-evolution of resources and processes with synchronization constrained by the availability of resources. We provide a logical characterization, analogous to Hennessy–Milner logic’s characterization of bisimulation in CCS, of bisimulation between resource processes which is compositional in the concurrent and local structure of systems.

Journal Article Editorial Get access David J. Pym David J. Pym HP Labs, Bristol and University of Bath Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 16, Issue 1, February 2006, Pages 1–3, https://doi.org/10.1093/logcom/exi069 Published: 01 February 2006

Editorial David Pym David Pym University of Bath, UK Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 15, Issue 6, December 2005, Page 819, https://doi.org/10.1093/logcom/exh054 Published: 01 December 2005

The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource that is rich enough, for example, to form the logical basis for ‘pointer logic’ and ‘separation logic’ semantics for programs that manipulate mutable data structures. We develop a theory of semantic tableaux for BI, so providing an elegant basis for efficient theorem proving tools for BI. It is based on the use of an algebra of labels for BI's tableaux to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, , the challenge consists in dealing with BI's Grothendieck topological models within such a proof-search method, based on labels. We prove soundness and completeness theorems for a resource tableaux method TBI with respect to this semantics and provide a way to build countermodels from so-called dependency graphs. Then, from these results, we can define a new resource semantics of BI, based on partially defined monoids, and prove that this semantics is complete. Such a semantics, based on partiality, is closely related to the semantics of BI's (intuitionistic) pointer and separation logics. Returning to the tableaux calculus, we propose a new version with liberalised rules for which the countermodels are closely related to the topological Kripke semantics of BI. As consequences of the relationships between semantics of BI and resource tableaux, we prove two new strong results for propositional BI: its decidability and the finite model property with respect to topological semantics.

It is well-known that weakening and contraction cause naive categorical models of the classical sequent calculus to collapse to Boolean lattices. We introduce sound and complete models that avoid this collapse by interpreting cut-reduction by a partial order between morphisms. We provide concrete examples of such models by applying the geometry-of-interaction construction to quantaloids with finite biproducts, and show how these models illuminate cut reduction in the presence of weakening and contraction. Our models make no commitment to any translation of classical logic into intuitionistic logic and distinguish non-deterministic choices of cut-elimination.

Editorial Get access David J. Pym David J. Pym University of Bath, Semantics Corner Editor Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 13, Issue 5, October 2003, Pages 633–638, https://doi.org/10.1093/logcom/13.5.633 Published: 01 October 2003

Forthcoming Papers David Pym David Pym Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 13, Issue 5, October 2003, Pages 799–800, https://doi.org/10.1093/logcom/13.5.799 Published: 01 October 2003

We consider the problem of searching for proofs in sequential presentations of logics with multiplicative (or intensional) connectives. Specifically, we start with the multiplicative fragment of linear logic and extend, on the one hand, to linear logic with its additives and, on the other, to the additives of the logic of bunched implications ( BI ). We give an algebraic method for calculating the distribution of the side-formulæ in multiplicative rules which allows the occurrence or non-occurrence of a formula on a branch of a proof to be determined once sufficient information is available. Each formula in the conclusion of such a rule is assigned a Boolean expression. As a search proceeds, a set of Boolean constraint equations is generated. We show that a solution to such a set of equations determines a proof corresponding to the given search. We explain a range of strategies, from the lazy to the eager, for solving sets of constraint equations. We indicate how to apply our methods systematically to large family of relevant systems.

The λΛ‐calculus is a dependent type theory with both linear and intuitionistic dependent function spaces. It can be seen to arise in two ways. Firstly, in logical frameworks, where it is the language of the RLF logical framework and can uniformly represent linear and other relevant logics. Secondly, it is a presentation of the proof‐objects of a structural variation, with Dereliction, of a fragment of BI, the logic of bunched implications. As such, it is also closely related to linear logic. BI is a logic which directly combines linear and intuitionistic implication and, in its predicate version, has both linear and intuitionistic quantifiers. The λΛ‐calculus is the dependent type theory which generalizes both implications and quantifiers. In this paper, we study the categorical semantics of the λΛ‐calculus, gives a theory of ‘Kripke resource models’, i.e. monoid‐indexed sets of functorial Kripke models, in which the monoid gives an account of resource consumption. A class of concrete, set‐theoretic models is given by the category of families of sets parametrized over a small monoidal category, in which the intuitionistic dependent function space is described in the established way, but the linear dependent function space is described using Day's tensor product.

We extend Parigot's λμ-calculus to form a system of realizers for classical logic which reflects the structure of Gentzen's cut-free, multiple-conclusioned, sequent calculus LK when used as a system for proof-search. Specifically, we add (i) a second binding operator, υ, which realizes classical, multiple-conclusioned disjunction, and (ii) explicit substitutions, ∈, which provide sufficient term-structure to interpret the left rules of LK. A necessary and sufficient condition is formulated on realizers to characterize when a given (classical) realizer for a sequent witnesses the intuitionistic provability of that sequent. A translation between the classical sequent calculus and classical resolution due to Mints is used to lift the conditions to classical resolution, thereby giving a characterization of the intuitionistic force of classical resolution. One application of these results is to allow standard resolution methods of uniform proof-search to be used directly for intuitionistic logic but, more significantly, they support a type-theoretic analysis of search spaces in both classical and intuitionistic logic.

We present the logic of bunched implications, BI, in which a multiplicative (or linear) and an additive (or intuitionistic) implication live side-by-side. The propositional version of BI arises from an analysis of the proof-theoretic relationship between conjunction and implication, and may be viewed as a merging of intuitionistic logic and multiplicative, intuitionistic linear logic. The predicate version of BI includes, in addition to usual additive quantifiers, multiplicative (or intensional) quantifiers /spl forall//sub new/, and /spl exist//sub new/, which arise from observing restrictions on structural rules on the level of terms as well as propositions. Moreover, these restrictions naturally allow the distinction between additive predication and multiplicative predication for each propositional connective. We provide a natural deduction system, a sequent calculus, a Kripke semantics and a BHK semantics for BI. We mention computational interpretations, based on locality and sharing, at both the propositional and predicate levels. We explain BI's relationship with intuitionistic logic, linear logic and other relevant logics.

We study a framework, RLF, for defining natural deduction presentations of linear and other relevant logics. RLF consists in a language together, in a manner similar to that of LF, with a representation mechanism. The language of RLF, the λλκ-calculus, is a system of first-order linear dependent function types which uses a function κ to describe the degree of sharing of variables between functions and their arguments. The representation mechanism is judgements-as-types, developed for linear and other relevant logics. The λλκ-calculus is a conservative extension of the λΠ-calculus and RLF is a conservative extension of LF.

In this paper we consider the problem of identifying logic programming languages for linear logic. Our analysis builds on a notion of goal-directed provability, characterized by the so-called uniform proofs, previously introduced for minimal and intuitionistic logic. A class of uniform proofs in linear logic is identified by an analysis of the permutability of inferences in the linear sequent calculus. We show that this class of proofs is complete (for logical consequence) for a certain (quite large) fragment of linear logic, which thus forms a logic programming language. We obtain a notion of resolution proof, in which only one left rule, of clause-directed resolution, is required. We also consider a translation, resembling those of Girard, of the hereditary Harrop fragment of intuitionistic logic into our framework. We show that goal-directed provability is preserved under this translation.