[Prev][Next][Index][Thread]
limited use of exponentials
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}")