System NEL is undecidable

DOI10.1016/S1571-0661(04)80853-3MaRDI QIDQ4924537zbMATH OpenFDO

Authors Lutz Straßburger

Publication date 6 June 2013

Published in Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S1571-0661(04)80853-3

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Recommendations

• A system of interaction and structure. V: The exponentials and splitting
• A system of interaction and structure. IV: The exponentials and decomposition
• scientific article; zbMATH DE number 1980929
• The undecidability of second order linear logic without exponentials
• Undecidability of multiplicative subexponential logic

Cites work

• A Local System for Classical Logic
• A system of interaction and structure
• Decision problems for propositional linear logic
• Games and full completeness for multiplicative linear logic
• How to Program an Infinite Abacus
• scientific article; zbMATH DE number 2185722 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 1980929 (Why is no real title available?)
• scientific article; zbMATH DE number 1841813 (Why is no real title available?)
• scientific article; zbMATH DE number 2090535 (Why is no real title available?)
• scientific article; zbMATH DE number 786490 (Why is no real title available?)
• Linear logic
• Linear logic as a logic of computations
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The complexity of Horn fragments of linear logic
• The mix rule
• The undecidability of second order linear logic without exponentials
• The undecidability of second order multiplicative linear logic

Cited in

(11)

• On the decision problem for MELL
• MELL in the calculus of structures
• The fixed point problem of a simple reversible language
• System BV is NP-complete
• A system of interaction and structure. IV: The exponentials and decomposition
• Linear lambda calculus and deep inference
• A system of interaction and structure. V: The exponentials and splitting
• scientific article; zbMATH DE number 4033715 (Why is no real title available?)
• A System of Interaction and Structure III: The Complexity of BV and Pomset Logic
• Deep inference in proof search: the need for shallow inference
• Lambek calculus with banged atoms for parasitic gaps

This page was built for publication: System NEL is undecidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4924537)