Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T23:12:10.740Z Has data issue: false hasContentIssue false

The undecidability theorem for the Horn-like fragment of linear logic (Revisited)

Published online by Cambridge University Press:  03 May 2016

MAX KANOVICH*
Affiliation:
University College London, UK. Email: m.kanovich@ucl.ac.ukNational Research University Higher School of Economics, Moscow, Russia
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

There has been an increased interest in the decision problems for linear logic and its fragments. Here, we give a fully self-contained, easy-to-follow, but fully detailed, direct and constructive proof of the undecidability of a very simple Horn-like fragment of linear logic, which is accessible to a wide range of people. Namely, we show that there is a direct correspondence between terminated computations of a Minsky machine M and cut-free linear logic derivations for a Horn-like sequent of the form

\begin{equation*}\bang{\Phi_M},\ l_1 \vdash l_0,\end{equation*}
where ΦM consists only of Horn-like implications of the following simple forms
\begin{equation*}(l \llto l'),\ \ ((l\otimes r) \llto l'),\ \ (l\llto (r\otimes l')),\ \ and \ \ (l\llto (l'\oplus l'')),\end{equation*}
where l1, l0, l, l′, l″ and r stand for literals.

Neither negation, nor &, nor constants, nor embedded implications/bangs are used here.

Furthermore, our particular correspondence constructed above provides decidability for each of the Horn-like fragments whenever we confine ourselves to any two forms of the above Horn-like implications, along with the complexity bounds that come from the proof.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2016