On the complexity of the Leibniz hierarchy

0503852 - ÚI 2020 RIV NL eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GBP202/12/G061; GA MŠMT(CZ) EF17_050/0008361
Institucionální podpora: RVO:67985807
Klíčová slova: Abstract algebraic logic * Leibniz hierarchy * Algebraizable logic * Protoalgebraic logic * Complexity theory
Obor OECD: Pure mathematics
Impakt faktor: 0.752, rok: 2019
Způsob publikování: Omezený přístup
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.
Trvalý link: http://hdl.handle.net/11104/0295627