4 found
Order:
Disambiguations
Patrick Lincoln [3]Patrick D. Lincoln [2]
  1.  42
    Decision problems for propositional linear logic.Patrick Lincoln, John Mitchell, Andre Scedrov & Natarajan Shankar - 1992 - Annals of Pure and Applied Logic 56 (1-3):239-311.
    Linear logic, introduced by Girard, is a refinement of classical logic with a natural, intrinsic accounting of resources. This accounting is made possible by removing the ‘structural’ rules of contraction and weakening, adding a modal operator and adding finer versions of the propositional connectives. Linear logic has fundamental logical interest and applications to computer science, particularly to Petri nets, concurrency, storage allocation, garbage collection and the control structure of logic programs. In addition, there is a direct correspondence between polynomial-time computation (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   43 citations  
  2.  41
    Linearizing intuitionistic implication.Patrick Lincoln, Andre Scedrov & Natarajan Shankar - 1993 - Annals of Pure and Applied Logic 60 (2):151-177.
    An embedding of the implicational propositional intuitionistic logic into the nonmodal fragment of intuitionistic linear logic is given. The embedding preserves cut-free proofs in a proof system that is a variant of IIL. The embedding is efficient and provides an alternative proof of the PSPACE-hardness of IMALL. It exploits several proof-theoretic properties of intuitionistic implication that analyze the use of resources in IIL proofs.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  3.  10
    Computational Aspects of Linear Logic.Patrick Lincoln - 1995 - MIT Press.
  4.  80
    (1 other version)Linear logic proof games and optimization.Patrick D. Lincoln, John C. Mitchell & Andre Scedrov - 1996 - Bulletin of Symbolic Logic 2 (3):322-338.
    § 1. Introduction. Perhaps the most surprising recent development in complexity theory is the discovery that the class NP can be characterized using a form of randomized proof checker that only examines a constant number of bits of the “proof” that a string is in a language [6, 5, 31, 3, 4]. More specifically, writing ∣x∣ for the length of a string x, a language L in the class NP of languages recognizable in Nondeterministic polynomial time is traditionally given by (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark