Disjunction Property and Complexity of Substructural Logics

Authors: Rostislav Horčík, K. Terui
Publication year: 2011
Publication type: Článek v odborném periodiku
Periodical: Theoretical Computer Science
Projects: Mathematical Fuzzy Logic in Computer Science
Fuzzy set theory as a foundation of fuzzy mathematics
Bibliographic citation: HORČÍK, Rostislav, TERUI, K. Disjunction Property and Complexity of Substructural Logics. Theoretical Computer Science. 2011, 412(31), 3992-4006. ISSN 0304-3975. E-ISSN 1879-2294
Dostupné z: doi:10.1016/j.tcs.2011.04.004
DOI: 10.1016/j.tcs.2011.04.004
ID: 368496

Abstract

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.