On NP-completeness in Linear Logic

Annals of Pure and Applied Logic 75 (1-2):137-152 (1995)
  Copy   BIBTEX

Abstract

In this paper the questions remaining open about NP-completeness of multiplicative and Horn fragments of the Linear Logic and the Linear Logic with the weakening rule are answered

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(94)00061-7

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,783

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The Semantics and Proof Theory of Linear Logic.Arnon Avron - 1988 - Theoretical Computer Science 57 (2):161-184.
Resolution calculus for the first order linear logic.Grigori Mints - 1993 - Journal of Logic, Language and Information 2 (1):59-83.
Synchronized Linear-Time Temporal Logic.Heinrich Wansing & Norihiro Kamide - 2011 - Studia Logica 99 (1-3):365-388.
Kripke semantics for modal substructural logics.Norihiro Kamide - 2002 - Journal of Logic, Language and Information 11 (4):453-470.
Completeness: from Gödel to Henkin.Maria Manzano & Enrique Alonso - 2014 - History and Philosophy of Logic 35 (1):1-26.
Temporal non-commutative logic: Expressing time, resource, order and hierarchy.Norihiro Kamide - 2009 - Logic and Logical Philosophy 18 (2):97-126.
Z-modules and full completeness of multiplicative linear logic.Masahiro Hamano - 2001 - Annals of Pure and Applied Logic 107 (1-3):165-191.
Games and full completeness for multiplicative linear logic.Abramsky Samson & Jagadeesan Radha - 1994 - Journal of Symbolic Logic 59 (2):543-574.
Axiomatising first-order temporal logic: Until and since over linear time.Mark Reynolds - 1996 - Studia Logica 57 (2-3):279 - 302.
Completeness results for linear logic on Petri nets.Uffe Engberg & Glynn Winskel - 1997 - Annals of Pure and Applied Logic 86 (2):101-135.
The Propositional Logic of Elementary Tasks.Giorgi Japaridze - 2000 - Notre Dame Journal of Formal Logic 41 (2):171-183.
RASP and ASP as a fragment of linear logic.Stefania Costantini & Andrea Formisano - 2013 - Journal of Applied Non-Classical Logics 23 (1-2):49-74.
Lambda Calculus and Intuitionistic Linear Logic.Simona Ronchi Della Rocca & Luca Roversi - 1997 - Studia Logica 59 (3):417-448.

Analytics

Added to PP
2014-01-16

Downloads
17 (#866,557)

6 months
13 (#192,902)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Add more references