| Links' Seminars and Public Events |   |
Fri, January 19, 2018 10:00 am 12:00 pm | Sylvain Salvati: "On magic set rewriting for Datalog" Cet exposé se veut une introduction à la transformation de programmes datalog. En particulier, je présenterai la transformation appelée "supplementary magic set rewriting" qui permet d'obtenir des programmes datalog dont l'évaluation semi-naïve se comporte de façon similaire à l'évaluation des programmes originaux par résolution SLD. Je montrerai l'algorithme et des exécutions de programmes sur des exemples issus de problèmes d'analyses grammaticales.  Lille B21 |
Fri, November 10, 2017 10:00 am 11:00 am | Momar Sakho: "Complexity of Certain Query Answering on Hyperstreams" A hyperstream is a sequence of streams with references to others. We study the complexity of computing certain answers for queries defined by automata and evaluated on hyperstreams of words. We show that the problem is PSPACE-complete for deterministic query automata, but that it can be solved in PTime for linear hyperstreams even with factorization. Salle B21 |
Fri, November 3, 2017 10:30 am 12:00 pm | Joanna Ochremiak, Paris 7: "Proof complexity of constraint satisfaction problems" Many natural computational problems, such as satisfiability and systems of equations, can be expressed in a unified way as constraint satisfaction problems (CSPs). In this talk I will show that the usual reductions preserving the complexity of the constraint satisfaction problem preserve also its proof complexity. As an application, I will present two gap theorems, which say that CSPs that admit small size refutations in some classical proof systems are exactly the constraint satisfaction problems which can be solved by Datalog. This is joint work with Albert Atserias. B21 |
