Number of the records: 1

Undecidability of Consequence Relation in Full Non-associative Lambek Calculus

SYSNO ASEP	0435915
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	Undecidability of Consequence Relation in Full Non-associative Lambek Calculus
Author(s)	Chvalovský, Karel (UIVT-O)_{SAI, RID, ORCID}
Source Title	Journal of Symbolic Logic. - : Cambridge University Press - ISSN 0022-4812 Roč. 80, č. 2 (2015), s. 567-586
Number of pages	20 s.
Language	eng - English
Country	US - United States
Keywords	substructural logics ; consequence relation ; undecidability ; tag systems ; word problem ; rewriting systems
Subject RIV	BA - General Mathematics
R&D Projects	GAP202/10/1826 GA ČR - Czech Science Foundation (CSF)
Institutional support	UIVT-O - RVO:67985807
UT WOS	000353308800009
EID SCOPUS	84928563737
DOI	10.1017/jsl.2014.39
Annotation	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 {., V} 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.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2016

Number of the records: 1