Complexity questions on linear logic

• To: types@theory.lcs.mit.edu, logic@theory.lcs.mit.edu
• Subject: Complexity questions on linear logic
• From: gunter@central.cis.upenn.edu
• Date: Sun, 4 Feb 90 12:12:33 EST
• In-Reply-To: John C. Mitchell's message of Sun, 4 Feb 90 09:40:35 EST <9002041440.AA00818@stork.lcs.mit.edu>
• Posted-Date: Sun, 4 Feb 90 12:12:33 EST

I'm also curious about the status of the propositional linear logic
decision problem.

Research on connections between Petri nets (vector addition systems)
and fragments of propositional linear logic has shown that the
decision problem for linear logic with the connectives:

  -o (linear implication)  ox  (tensor product)  ! (of course)

must be at least has hard as the decision problem for forward
markings.  Since the latter was a significant topic of research for
some time, it seems that propositional linear logic (with the
modalities) must encode some quite difficult decision problems.

---carl gunter

• Prev: Complexity questions on linear logic
• Next: Complexity questions on linear logic
• Index(es):
  • Main
  • Thread