Journal of Symbolic Logic 61 (2):541-548 (1996)

Abstract
Recently, Lincoln, Scedrov and Shankar showed that the multiplicative fragment of second order intuitionistic linear logic is undecidable, using an encoding of second order intuitionistic logic. Their argument applies to the multiplicative-additive fragment, but it does not work in the classical case, because second order classical logic is decidable. Here we show that the multiplicative-additive fragment of second order classical linear logic is also undecidable, using an encoding of two-counter machines originally due to Kanovich. The faithfulness of this encoding is proved by means of the phase semantics
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275674
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 54,646
Through your library

References found in this work BETA

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

A Modal View of Linear Logic.Simone Martini & Andrea Masini - 1994 - Journal of Symbolic Logic 59 (3):888-899.
Linguistic Applications of First Order Intuitionistic Linear Logic.Richard Moot & Mario Piazza - 2001 - Journal of Logic, Language and Information 10 (2):211-232.
The Logic of Bunched Implications.Peter W. O'Hearn & David J. Pym - 1999 - Bulletin of Symbolic Logic 5 (2):215-244.
Interpolation in Fragments of Classical Linear Logic.Dirk Roorda - 1994 - Journal of Symbolic Logic 59 (2):419-444.
Undecidability and Intuitionistic Incompleteness.D. C. McCarty - 1996 - Journal of Philosophical Logic 25 (5):559 - 565.
An Event-Based Fragment of First-Order Logic Over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.

Analytics

Added to PP index
2009-01-28

Total views
102 ( #94,522 of 2,385,946 )

Recent downloads (6 months)
2 ( #369,659 of 2,385,946 )

How can I increase my downloads?

Downloads

My notes