Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T12:40:07.471Z Has data issue: false hasContentIssue false

FULL LAMBEK CALCULUS WITH CONTRACTION IS UNDECIDABLE

Published online by Cambridge University Press:  10 May 2016

KAREL CHVALOVSKÝ
Affiliation:
INSTITUTE OF COMPUTER SCIENCE ACADEMY OF SCIENCES OF THE CZECH REPUBLIC POD VODÁRENSKOU VĚŽÍ 2 182 07 PRAGUE 8, CZECH REPUBLIC E-mail: chvalovsky@cs.cas.cz
ROSTISLAV HORČÍK
Affiliation:
INSTITUTE OF COMPUTER SCIENCE ACADEMY OF SCIENCES OF THE CZECH REPUBLIC POD VODÁRENSKOU VĚŽÍ 2 182 07 PRAGUE 8, CZECH REPUBLIC E-mail: horcik@cs.cas.cz
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.

We prove that the set of formulae provable in the full Lambek calculus with the structural rule of contraction is undecidable. In fact, we show that the positive fragment of this logic is undecidable.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2016