Počet záznamů: 1

Disjunction Property and Complexity of Substructural Logics

  1. 1.
    0368496 - UIVT-O 2012 RIV NL eng J - Článek v odborném periodiku
    Horčík, Rostislav - Terui, K.
    Disjunction Property and Complexity of Substructural Logics.
    Theoretical Computer Science. Roč. 412, č. 31 (2011), s. 3992-4006 ISSN 0304-3975
    Grant CEP: GA ČR GAP202/10/1826; GA MŠk ME09110
    Výzkumný záměr: CEZ:AV0Z10300504
    Klíčová slova: substructural logics * disjunction property * computational complexity
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.665, rok: 2011

    We systematically identify a large class of substructural logics that satisfy the disjunction property (DP), and show that every consistent substructural logic with the DP is PSPACE-hard. Our results are obtained by using algebraic techniques. PSPACE-completeness for many of these logics is furthermore established by proof theoretic arguments.
    Trvalý link: http://hdl.handle.net/11104/0202825
    Název souboruStaženoVelikostKomentářVerzePřístup
    0368496.pdf0642.3 KBAutorský preprintpovolen