A new proof search method for linear logic (Q4217606)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1222110
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A new proof search method for linear logic |
scientific article; zbMATH DE number 1222110 |
Statements
16 March 2000
0 references
multiplicative and additive linear logic
0 references
proof-search
0 references
proof-structure
0 references
proof-nets
0 references
correctness criterion
0 references
boolean weights
0 references
algorithm
0 references
polynomial time
0 references
0.8278806209564209
0 references
0.8174916505813599
0 references
0.8139371275901794
0 references
A new proof search method for linear logic (English)
0 references
In Lect. Notes Pure Appl. Math. 180, 97-124 (1996; Zbl 0868.03025), \textit{J.-Y. Girard} introduced a new syntax for proof-nets of multiplicative and additive Linear Logic (MALL): boxes for the additives are removed, and a correctness criterion (in the Danos-Regnier style) making use of ``boolean weights'' is given. The notion of superimposition (of formulas, links, subproof-nets) is very complex, not well understood, and tighly linked to the additive connective \(\&\): this makes the theory of MALL proof-nets very difficult. However, provability in MALL is decidable (in fact PSPACE-complete), as proven by \textit{P. Lincoln, J. Mitchell, A. Scedrov} and \textit{N. Shankar} [Ann. Pure Appl. Logic 56, No. 1-3, 239-311 (1992; Zbl 0768.03003)]. This paper proposes a nice variant of Girard's correctness criterion for cut-free proof-nets, which yields a proof search method for MALL. The author first gives an algorithm to build a (cut-free) proof-structure (in the sense of Girard) from a given sequent. He then introduces his variant of the correctness criterion for cut-free proof-nets, and shows it can be checked in polynomial time (in the size of the proof-structure). The main novelty in the criterion is the notion of ``inductive empire'' of a formula, in terms of which the now standard acyclicity and connectedness condition can be expressed. For the entire collection see [Zbl 0892.00029].
0 references