datum: 11.1.2017 v 10:00
název: On the complexity of the Leibniz hierarchy
přednášející: Tommaso Moraschini (UI)
místo konání: UI, 2.patro, místnost č.318

souhrn: Abstract algebraic logic is a theory that provides general tools for the uniform study of propositional logic. One of its main achievements is that so-called Leibniz hierarchy, where logics are classified according to properties related to the definability of logical equivalence and of truth predicates. It is known that the problem of classifying a semantically-presented logic in the Leibniz hierarchy is decidable. In this talk we investigate the computational complexity of this problem and show that it is complete for EXPTIME.