Disjunction Property and Complexity of Substructural Logics

0368496 - ÚI 2012 RIV NL eng J - Journal Article
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
R&D Projects: GA ČR GAP202/10/1826; GA MŠMT ME09110
Institutional research plan: CEZ:AV0Z10300504
Keywords : substructural logics * disjunction property * computational complexity
Subject RIV: BA - General Mathematics
Impact factor: 0.665, year: 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.
Permanent Link: http://hdl.handle.net/11104/0202825