Isolating Resource Consumption in Linear Logic Proof Search: Extended abstract

The Complexity of Local Proof Search in

The Complexity of Local Proof Search in Linear Logic: (Extended Abstract)

✍ Patrick D. Lincoln; John C. Mitchell; Andre Scedrov 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 473 KB

Proof search in linear logic is known to be di cult: the provability of propositional linear logic formulas is undecidable. Even without the modalities, multiplicativeadditive fragment of propositional linear logic, mall, i s k n o wn to be pspace-complete, and the pure multiplicative fragment, mll,