Undecidability of Consequence Relation in Full Non-associative Lambek Calculus

0435915 - ÚI 2016 RIV US eng J - Journal Article
Chvalovský, Karel
Undecidability of Consequence Relation in Full Non-associative Lambek Calculus.
Journal of Symbolic Logic. Roč. 80, č. 2 (2015), s. 567-586. ISSN 0022-4812. E-ISSN 1943-5886
R&D Projects: GA ČR GAP202/10/1826
Institutional support: RVO:67985807
Keywords : substructural logics * consequence relation * undecidability * tag systems * word problem * rewriting systems
Subject RIV: BA - General Mathematics
Impact factor: 0.510, year: 2015

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.
Permanent Link: http://hdl.handle.net/11104/0239734