On the complexity of the Leibniz hierarchy

DOI10.1016/j.apal.2019.02.003OpenAlexW2920555127WikidataQ123260237 ScholiaQ123260237MaRDI QIDQ1740630

Tommaso Moraschini

Publication date: 2 May 2019

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1908.00924

zbMATH Keywords

abstract algebraic logicalgebraizable logicprotoalgebraic logiccomplexity theoryLeibniz hierarchy

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Equational logic, Mal'tsev conditions (08B05) Equational classes, universal algebra in model theory (03C05) Abstract algebraic logic (03G27)

Related Items (3)

ON EQUATIONAL COMPLETENESS THEOREMS ⋮ The poset of all logics. III: Finitely presentable logics ⋮ THE POSET OF ALL LOGICS I: INTERPRETATIONS AND LATTICE STRUCTURE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Update to ``A survey of abstract algebraic logic
• Reduced products of logical matrices
• Characterizing Mal'cev conditions
• Algebraic semantics for deductive systems
• A computational glimpse at the Leibniz and Frege hierarchies
• Order algebraizable logics
• Equivalence of consequence operations
• A perspective on the algebra of logic
• Some characterization theorems for infinitary universal Horn logic without equality
• The lattice of interpretability types of varieties
• Correspondences between gentzen and hilbert systems
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• Algebraizable logics
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• FINDING TYPE SETS IS NP-HARD
• The structure of finite algebras
• A STUDY OF TRUTH PREDICATES IN MATRIX SEMANTICS
• Assertional logics, truth-equational logics, and the hierarchies of abstract algebraic logic
• The shape of congruence lattices
• THE POSET OF ALL LOGICS I: INTERPRETATIONS AND LATTICE STRUCTURE
• Computational Complexity
• On the Computational Complexity of Algorithms
• Two Mal'cev-type theorems in universal algebra
• Protoalgebraic logics

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