Nadcházející semináře

  • Tommaso Moraschini: On the complexity of the Leibniz hierarchy

    11.1.2017 10:00 @ Applied Mathematical Logic

    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 classi_ed according to properties related to the de_nability 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.

  • Rostislav Horčík: Algebraic Approach to Valued CSP via Non-classical Logics

    18.1.2017 10:00 @ Applied Mathematical Logic

    CSP provides a uniform framework to analyze and solve many combinatorial problems. Similarly valued CSP might be seen as a uniform framework to study a wide class of problems coming from combinatorial optimization such as Maximum Independent Set. A major research line in CSP tries to _nd a boundary between tractable and intractable problems. One of the most successful approaches to classify tractable problems is the algebraic one based on Geiger