Number of the records: 1

On the complexity of the Leibniz hierarchy

SYSNO ASEP	0503852
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	On the complexity of the Leibniz hierarchy
Author(s)	Moraschini, Tommaso (UIVT-O)_{SAI, RID}
Source Title	Annals of Pure and Applied Logic. - : Elsevier - ISSN 0168-0072 Roč. 170, č. 7 (2019), s. 805-824
Number of pages	20 s.
Publication form	Print - P
Language	eng - English
Country	NL - Netherlands
Keywords	Abstract algebraic logic ; Leibniz hierarchy ; Algebraizable logic ; Protoalgebraic logic ; Complexity theory
Subject RIV	BA - General Mathematics
OECD category	Pure mathematics
R&D Projects	GBP202/12/G061 GA ČR - Czech Science Foundation (CSF)
	EF17_050/0008361 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
Method of publishing	Limited access
Institutional support	UIVT-O - RVO:67985807
UT WOS	000467892300002
EID SCOPUS	85062281263
DOI	10.1016/j.apal.2019.02.003
Annotation	We prove that the problem of determining whether a finite logical matrix determines an algebraizable logic is complete for EXPTIME. The same result holds for the classes of order algebraizable, weakly algebraizable, equivalential and protoalgebraic logics. Finally, the same problem for the class of truth-equational logic is shown to be hard for EXPTIME.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2020
Electronic address	http://dx.doi.org/10.1016/j.apal.2019.02.003

Number of the records: 1