On the complexity of the Leibniz hierarchy

DOI10.1016/J.APAL.2019.02.003arXiv1908.00924WikidataQ123260237 ScholiaQ123260237MaRDI QIDQ6323101

Publication date: 1 August 2019

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.

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Equational logic, Mal'tsev conditions (08B05) Abstract algebraic logic (03G27)

This page was built for publication: On the complexity of the Leibniz hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323101)