Linear logic with fixed resources (Q1326773): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q677074 |
||
Property / author | |||
Property / author: Dmitri A. Archangelsky / rank | |||
Revision as of 16:05, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear logic with fixed resources |
scientific article |
Statements
Linear logic with fixed resources (English)
0 references
8 June 1995
0 references
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.
0 references
proof theory
0 references
models
0 references
nonexponential algorithm checking provability and providing a proof
0 references
linear logic with modalities
0 references
provability
0 references
sequent
0 references
net of communication
0 references