Linear logic with fixed resources (Q1326773): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Linear logic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The linear abstract machine / rank | |||
Normal rank |
Revision as of 16:25, 22 May 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