Number of the records: 1

Disjunction Property and Complexity of Substructural Logics

SYSNO ASEP	0368496
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	Disjunction Property and Complexity of Substructural Logics
Author(s)	Horčík, Rostislav (UIVT-O)_{SAI, RID} Terui, K. (JP)
Source Title	Theoretical Computer Science. - : Elsevier - ISSN 0304-3975 Roč. 412, č. 31 (2011), s. 3992-4006
Number of pages	15 s.
Language	eng - English
Country	NL - Netherlands
Keywords	substructural logics ; disjunction property ; computational complexity
Subject RIV	BA - General Mathematics
R&D Projects	GAP202/10/1826 GA ČR - Czech Science Foundation (CSF)
	ME09110 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
CEZ	AV0Z10300504 - UIVT-O (2005-2011)
UT WOS	000292353400002
EID SCOPUS	79958066909
DOI	10.1016/j.tcs.2011.04.004
Annotation	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.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2012

Number of the records: 1