Undecidability of multiplicative subexponential logic

Kaustuv Chaudhuri

doi:10.4204/EPTCS.176.1

Undecidability of multiplicative subexponential logic

Research output: Contribution to journal › Conference article › peer-review

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.

Original language	English
Pages (from-to)	1-8
Number of pages	8
Journal	Electronic Proceedings in Theoretical Computer Science, EPTCS
Volume	176
DOIs	https://doi.org/10.4204/EPTCS.176.1
Publication status	Published - 16 Feb 2015
Event	3rd International Workshop on Linearity, LINEARITY 2014 - Vienna, Austria Duration: 13 Jul 2014 → …

Access to Document

10.4204/EPTCS.176.1

Cite this

@article{b24171b39f5b424b8cc519861579cd58,

title = "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.",

author = "Kaustuv Chaudhuri",

year = "2015",

month = feb,

day = "16",

doi = "10.4204/EPTCS.176.1",

language = "English",

volume = "176",

pages = "1--8",

journal = "Electronic Proceedings in Theoretical Computer Science, EPTCS",

issn = "2075-2180",

note = "3rd International Workshop on Linearity, LINEARITY 2014 ; Conference date: 13-07-2014",

}

TY - JOUR

T1 - Undecidability of multiplicative subexponential logic

AU - Chaudhuri, Kaustuv

PY - 2015/2/16

Y1 - 2015/2/16

N2 - 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.

AB - 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.

U2 - 10.4204/EPTCS.176.1

DO - 10.4204/EPTCS.176.1

M3 - Conference article

AN - SCOPUS:84952668382

SN - 2075-2180

VL - 176

SP - 1

EP - 8

JO - Electronic Proceedings in Theoretical Computer Science, EPTCS

JF - Electronic Proceedings in Theoretical Computer Science, EPTCS

T2 - 3rd International Workshop on Linearity, LINEARITY 2014

Y2 - 13 July 2014

ER -

Undecidability of multiplicative subexponential logic

Abstract

Access to Document

Fingerprint

Cite this