On the complexity of the Leibniz hierarchy

DOI10.1016/J.APAL.2019.02.003MaRDI QIDQ6323101arXivWikidataFDO

Authors Tommaso Moraschini

Publication date 1 August 2019

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.APAL.2019.02.003

Mathematics Subject Classification ID

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

arXiv classification

math.LO

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.

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)