Počet záznamů: 1
Disjunction Property and Complexity of Substructural Logics
- 1.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
Název souboru Staženo Velikost Komentář Verze Přístup 0368496.pdf 0 642.3 KB Autorský preprint povolen
Počet záznamů: 1