0435915 - ÚI 2016 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GAP202/10/1826
Institucionální podpora: RVO:67985807
Klíčová slova: substructural logics * consequence relation * undecidability * tag systems * word problem * rewriting systems
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.510, rok: 2015 ; AIS: 0.724, rok: 2015
DOI: https://doi.org/10.1017/jsl.2014.39

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.
Trvalý link: http://hdl.handle.net/11104/0239734