On the complexity of the Leibniz hierarchy

Autoři: Tommaso Moraschini
Rok vydání: 2019
Typ publikace: Článek v odborném periodiku
Periodikum: Annals of Pure and Applied Logic
Projekty: Centrum excelence - Institut teoretické informatiky (CE-ITI)
Rozvoj lidských zdrojů pro výzkum v teoretické informatice
Bibliografická citace: MORASCHINI, Tommaso. On the complexity of the Leibniz hierarchy. Annals of Pure and Applied Logic. 2019, 170(7), 805-824. ISSN 0168-0072. E-ISSN 1873-2461
Dostupné z: doi:10.1016/j.apal.2019.02.003.
DOI: 10.1016/j.apal.2019.02.003
ID: 503852
Online záznam: Zobrazit online záznam

Abstrakt

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.