Hostname: page-component-7b7567c8c-9cwtv Total loading time: 0 Render date: 2026-11-19T19:33:28.804Z Has data issue: false hasContentIssue false

UNDECIDABILITY OF CONSEQUENCE RELATION IN FULL NON-ASSOCIATIVE LAMBEK CALCULUS

Published online by Cambridge University Press:  22 April 2015

KAREL CHVALOVSKÝ*
Affiliation:
INSTITUTE OF COMPUTER SCIENCE ACADEMY OF SCIENCES OF THE CZECH REPUBLIC POD VODÁRENSKOUVĚŽÍ 271/2, 182 07 PRAGUE 8, CZECH REPUBLICE-mail:karel@chvalovsky.czURL: http://karel.chvalovsky.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 consequence relation in the Full Non-associative Lambek Calculus is undecidable. An encoding of the halting problem for 2-tag systems using finitely many sequents in the language {⋅,∨} is presented. Therefore already the consequence relation in this fragment is undecidable. Moreover, the construction works even when the structural rules of exchange and contraction are added.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2015