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

      0 references
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references