Number of the records: 1  

Undecidability of Consequence Relation in Full Non-associative Lambek Calculus

  1. 1.
    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

     
    FileDownloadSizeCommentaryVersionAccess
    a0435915.pdf5373.1 KBPublisher’s postprintrequire
    0435915.pdf21 MBAuthor´s preprintrequire
     
Number of the records: 1