Disjunction Property and Complexity of Substructural Logics

0368496 - ÚI 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. E-ISSN 1879-2294
Grant CEP: GA ČR GAP202/10/1826; GA MŠMT 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