On the complexity of the Leibniz hierarchy |
| |
| Authors: | Tommaso Moraschini |
| |
| Affiliation: | Institute of Computer Science, Academy of Sciences of Czech Republic, Pod Vodárenskou vě?í 271/2, 182 07 Prague 8, Czech Republic |
| |
| Abstract: | 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. |
| |
| Keywords: | 03G27 03D15 03C05 08B05 Abstract algebraic logic Leibniz hierarchy Algebraizable logic Protoalgebraic logic Complexity theory |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
