The undecidability of second order multiplicative linear logic

DOI10.1006/inco.1996.0019zbMath0852.03003OpenAlexW1966857180MaRDI QIDQ1917079

Yves Lafont, Andrej Scedrov

Publication date: 5 December 1996

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

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

zbMATH Keywords

undecidabilityphase semanticscounter machinesmultiplicative fragment of second-order propositional linear logic

Mathematics Subject Classification ID

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

Related Items (9)

Language models for some extensions of the Lambek calculus ⋮ Phase semantics for light linear logic ⋮ A PSPACE-complete fragment of second-order linear logic ⋮ On the decision problem for MELL ⋮ The finite model property for various fragments of linear logic ⋮ System NEL is Undecidable ⋮ Encoding Hamiltonian circuits into multiplicative linear logic ⋮ Linear concurrent constraint programming: Operational and phase semantics ⋮ A uniform semantic proof for cut-elimination and completeness of various first and higher order logics.

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