A Local System for Linear Logic

Niveau: Supérieur
A Local System for Linear Logic Lutz Straßburger Technische Universitat Dresden, Fakultat Informatik, 01062 Dresden, Germany Abstract. In this paper I will present a deductive system for linear logic, in which all rules are local. In particular, the contraction rule is reduced to an atomic version, and there is no global promotion rule. In order to achieve this, it is necessary to depart from the sequent calculus and use the calculus of structures, which is a generalization of the one-sided sequent calculus. In a rule, premise and conclusion are not sequents, but structures, which are expressions that share properties of formulae and sequents. 1 Introduction Since distributed computation moves more and more into the focus of research in theoretical computer science, it is also of interest to implement proof search in deductive systems in a distributed way. For this, it is desirable that the appli- cation of each inference rule consumes only a bounded amount of computational resources, i.e. time and space. But most deductive systems contain inference rules that do not have this property. Let me use as an example the well-known sequent calculus system for linear logic [5] (see Fig. 4). In particular, consider the following three rules, ,?A, ?A,? ?c ,?A,? , , A,? , B,? ! , A!B,? and , A,

• inference rules


• called


• since distributed


• contraction rule


• local system


• calculus


• sequent calculus


• global view


• like cut