Počet záznamů: 1  

Undecidability of Consequence Relation in Full Non-associative Lambek Calculus

  1. 1. 0435915 - UIVT-O 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
    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

    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
    Název souboruStaženoVelikostKomentářVerzePřístup
    0435915.pdf21 MBAutorský preprintvyžádat