Disjunction Property and Complexity of Substructural Logics

Autoři: Rostislav Horčík
Rok vydání: 2011
Typ publikace: Článek v odborném periodiku
Periodikum: Theoretical Computer Science
Projekty: Matematická fuzzy logika v informatice
Fuzzy teorie množin jakožto základ fuzzy matematiky
Bibliografická citace: 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

Abstrakt

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.