Linear logic with fixed resources (Q1326773): Difference between revisions

This paper aims at providing a variant of linear logic with modalities, for which a non-exponential algorithm checks provability and provides a proof for a given sequent. This contrasts with NP-completeness of this problem for the Horn fragment of linear logic. Linearity is understood as a control on availability of two sorts of supplies: variables and `convertors', that is, linear implications between conjunctions of variables. This is specified at each node of a fixed net of communication, having the form of a tree. Availability of modalities is treated in a way similar to Kripke models. This models to define truth of a sequent of a node; but also to elaborate a proof system with axioms attached to available supplies. Using a rather technical reduction to `canonical proofs', soundness and completeness are proven. Finally, the authors provide the announced algorithm.