Papex

Open problem · Computer science · Open

Decidability of multiplicative-exponential linear logic

Is there an algorithm that decides entailment in multiplicative-exponential linear logic (MELL)?

Summary

Linear logic, proposed by Jean-Yves Girard, treats assumptions as resources. Entailment in full linear logic is undecidable, and MELL is at least EXPSPACE-hard by a reduction from Petri net reachability; a 2015 proof of decidability published in Theoretical Computer Science was later shown to be erroneous.

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 18 Nov 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing