Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Abstract : Subexponential logic is a variant of linear logic with a family of exponential connectives---called subexponentials---that are indexed and arranged in a pre-order. Each subexponential has or lacks associated structural properties of weakening and contraction. We show that classical propositional multiplicative linear logic extended with one unrestricted and two incomparable linear subexponentials can encode the halting problem for two register Minsky machines, and is hence undecidable.
https://hal.inria.fr/hal-00998753 Contributor : Kaustuv ChaudhuriConnect in order to contact the contributor Submitted on : Monday, June 2, 2014 - 4:22:03 PM Last modification on : Thursday, January 20, 2022 - 5:30:46 PM Long-term archiving on: : Tuesday, September 2, 2014 - 12:45:17 PM
Kaustuv Chaudhuri. Undecidability of Multiplicative Subexponential Logic. Proceedings of the Third International Workshop on Linearity, Jul 2014, Vienna, Austria. pp.1--8, ⟨10.4204/EPTCS.176.1⟩. ⟨hal-00998753⟩