Number of the records: 1
Disjunction Property and Complexity of Substructural Logics
- 1.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
File Download Size Commentary Version Access 0368496.pdf 0 642.3 KB Author´s preprint open-access
Number of the records: 1