| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Undecidability of Multiplicative Subexponential Logic
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.
Cited literature [13 references]
https://hal.inria.fr/hal-00998753
Contributor : Kaustuv Chaudhuri <>
Submitted on : Monday, June 2, 2014 - 4:22:03 PM
Last modification on : Thursday, January 7, 2021 - 3:40:14 PM
Long-term archiving on: : Tuesday, September 2, 2014 - 12:45:17 PM
Contributor : Kaustuv Chaudhuri <>
Submitted on : Monday, June 2, 2014 - 4:22:03 PM
Last modification on : Thursday, January 7, 2021 - 3:40:14 PM
Long-term archiving on: : Tuesday, September 2, 2014 - 12:45:17 PM
Files
main.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution - NoDerivatives 4.0 International License