On the complexity of the Leibniz hierarchy

0503852 - ÚI 2020 RIV NL eng J - Journal Article
Moraschini, Tommaso
On the complexity of the Leibniz hierarchy.
Annals of Pure and Applied Logic. Roč. 170, č. 7 (2019), s. 805-824. ISSN 0168-0072. E-ISSN 1873-2461
R&D Projects: GA ČR GBP202/12/G061; GA MŠMT(CZ) EF17_050/0008361
Institutional support: RVO:67985807
Keywords : Abstract algebraic logic * Leibniz hierarchy * Algebraizable logic * Protoalgebraic logic * Complexity theory
OECD category: Pure mathematics
Impact factor: 0.752, year: 2019
Method of publishing: Limited access
http://dx.doi.org/10.1016/j.apal.2019.02.003

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.
Permanent Link: http://hdl.handle.net/11104/0295627