On the decision problem for MELL - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2019

On the decision problem for MELL

Résumé

In this short paper I will exhibit several mistakes in the recent attempt by Bimbó [3] to prove the decidability of the multiplicative exponential fragment of linear logic (MELL). In fact, the main mistake is so serious that there is no obvious fix, and therefore the decidability of MELL remains an open problem. As a side effect, this paper contains a complete (syntactic) proof of the decidability of the relevant version of MELL (called RMELL in this paper), that is the logic obtained from MELL by replacing the linear logic contraction rule by a general unrestricted version of the contraction rule. This proof can also be found (with a small error) in [3], and a semantic proof can be found in [35].
Fichier principal
Vignette du fichier
OnDeciMELL.pdf (168.97 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02386746 , version 1 (29-11-2019)

Identifiants

Citer

Lutz Strassburger. On the decision problem for MELL. Theoretical Computer Science, 2019, 768, pp.91-98. ⟨10.1016/j.tcs.2019.02.022⟩. ⟨hal-02386746⟩
34 Consultations
122 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More