limited use of exponentials

• To: LINEAR@EDU.Stanford.CS
• Subject: limited use of exponentials
• From: Serena Cerrito <serena@fr.lri>
• Date: Thu, 8 Jul 1993 18:07:57 +0200
• Approved: types@dcs.gla.ac.uk

Does anybody knows something about decidability (indecidability)
results for FRAGMENTS of linear logic involving a RESTRICTED use
of EXPONENTIALS (where the ``!" modality could be applied just
to formulae of a given simple form) ?  If yes, I would greatly appreciate
any indication of papers which I could look at.

Thanks in advance.

				Serenella Cerrito




moderators note: there are a few results along these these lines.
Prop LL is undecidable even if there are only negative !, and only
wrapping "small" formulas (with two connectives (-o and either * or +) 
and three propositional atoms).  Two sided Tensor Bang LL is decidable
for arbitrary uses of !.  M. Kanovich claims constant-only prop LL
is undecidable, but hasn't published his proof yet.

	@inproceedings(
CL92, 	Author = "J. Chirimar and J. Lipton",
	title = "{Provability in TBLL: A Decision Procedure}",
        Booktitle="Computer Science Logic '91",
	year = "1992",
	publisher = "{\it Lecture Notes in Computer Science, Springer}")

	@article(
LMSS92,	Author="Lincoln, P. and Mitchell, J. and Scedrov, A. and Shankar, N.",
	Title="Decision Problems for Propositional Linear Logic",
	Journal="Annals Pure Appl. Logic",
	Volume="56",
        Year="1992",
	pages="239-311",   
        Note="{Special Volume dedicated to the memory of John Myhill}") 

• Prev: No Subject
• Next: LICS'94 Call for Papers
• Index(es):
  • Main
  • Thread