Paper Info
Title
UNDECIDABILITY OF CONSEQUENCE RELATION IN FULL NON-ASSOCIATIVE LAMBEK CALCULUS
Abstract
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 {., boolean OR} 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.
Year
DOI
Venue
2015
10.1017/jsl.2014.39
JOURNAL OF SYMBOLIC LOGIC
Keywords
DocType
Volume
Substructural logics,consequence relation,undecidability,tag systems,word problem,rewriting systems
Journal
80
Issue
ISSN
Citations 
2
0022-4812
2
PageRank 
References 
Authors
0.42
7
1
Name
Order
Citations
PageRank
Karel Chvalovský1111.85