The undecidability of second order linear logic without exponentials

DOI10.2307/2275674zbMath0866.03005OpenAlexW2006177255MaRDI QIDQ4894725

Yves Lafont

Publication date: 7 October 1996

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e98c5b79de095d339aaab53793a828e2b5313676

zbMATH Keywords

undecidabilityphase semanticsencoding of two-counter machinesmultiplicative-additive fragment of second order classical linear logic

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (6)

Language models for some extensions of the Lambek calculus ⋮ Phase semantics for light linear logic ⋮ A PSPACE-complete fragment of second-order linear logic ⋮ Word problem for knotted residuated lattices. ⋮ System NEL is Undecidable ⋮ Encoding Hamiltonian circuits into multiplicative linear logic

Cites Work

• Linear logic
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Decision problems for propositional linear logic
• How to Program an Infinite Abacus
• Some Syntactical Observations on Linear Logic

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