The undecidability of second order multiplicative linear logic

DOI10.1006/INCO.1996.0019MaRDI QIDQ1917079zbMATH OpenOpenAlexFDO

Authors Yves Lafont, Andre Scedrov

Publication date 5 December 1996

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1006/inco.1996.0019

zbMATH Keywords

counter machinesundecidabilityphase semanticsmultiplicative fragment of second-order propositional linear logic

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10) Proof theory and constructive mathematics (03F99)

Recommendations

• The undecidability of second order linear logic without exponentials
• scientific article; zbMATH DE number 1163987
• scientific article; zbMATH DE number 1114339
• Decision problems for propositional linear logic

Cited in

(17)

• On the decision problem for MELL
• System NEL is undecidable
• The finite model property for various fragments of linear logic
• Encoding Hamiltonian circuits into multiplicative linear logic
• Decision problems for propositional linear logic
• Phase semantics for light linear logic
• A uniform semantic proof for cut-elimination and completeness of various first and higher order logics.
• A By-Level Analysis of Multiplicative Exponential Linear Logic
• scientific article; zbMATH DE number 408788 (Why is no real title available?)
• Undecidability results on two-variable logics
• First-order linear logic without modalities is NEXPTIME-hard
• Linear concurrent constraint programming: Operational and phase semantics
• The decidability of the intensional fragment of classical linear logic
• Undecidability of multiplicative subexponential logic
• Language models for some extensions of the Lambek calculus
• Synthetic Undecidability of MSELL via FRACTRAN Mechanised in Coq
• A PSPACE-complete fragment of second-order linear logic

This page was built for publication: The undecidability of second order multiplicative linear logic

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