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 |
Fri, October 13, 2017 11:00 am 1:00 pm | Dimitri Gallois: On parallel rewriting B21 |
Fri, September 29, 2017 10:00 am 12:00 pm | Nicolas Bacquey: "An algorithm for deciding the equivalence of tree transducers" As an extension of word transformations, tree transformations have numerous applications in computer science : XSLT transformations, Unix packages installation and removal, databases queries... Likewise, there are many formal models to describe these transformations. However, the proof of formal properies on these models is often difficult, or even undecidable. In this talk, I will be interested in one of the simplest model for tree transformations, namely deterministic top-down tree transducers (DTOP). It has been known for a while that the equivalence problem of DTOPs can be solved via an earliest normal form comparison algorithm, that is in 2EXPTIME. However, when applying this algorithm to practical cases, it seemed that the worst case was not bound to happen often, if ever. I will present a new algorithm for the problem, based on the search of counterexamples via the expansion and unification of a set of rules over states of DTOPs. The most interesting feature of this algorithm is that it runs in exponential time, thus proving that the equivalence problem of DTOPs is in fact EXPTIME-complete. Lille B31 |
Thu, July 6, 2017 all day | ANR Headwork: General Meeting Rennes |
Fri, June 16, 2017 all day | 09h15-09h45 Coffee Welcome 09h45-10h30 Michel de Rougemont: Approximate integration of streaming graph edges 10h30-11h15 Florent Cappelli: Understanding the complexity of #SAT using knowledge compilation 11h15-11h45 Yann Strozecki: Enumerating maximal solutions of saturation problems 12h00 Lunch 14h00 Discussion libre 16h00 End Inria Lille |
Thu, June 15, 2017 all day | 09h15-09h45 Welcome coffee 09h45-10h30 Pierre Bourhis: Introduction of circuit from database queries 10h30-11h15 Jen Keppeler: Answering FO+MOD queries under updates on bounded degree databases 11h15-12h00 Antoine Amarilli: Enumeration of valuation of circuits 12h00-13h30 Lunch + Café 13h30-14h30 Jan Ramon: Question around IA 14h30-15h15 Ahmet Kara: Covers of Query Results 15h15-15h45 Break 15h45-16h30 Alexandre Vigny: Constant delay enumeration for FO queries over databases with local bounded expansion 20h00 Dinner at Le Palermo Inria Lille |
Fri, June 9, 2017 10:30 am 12:30 pm | Valentin Montmirail: "A Recursive Shortcut for CEGAR: Application to the Modal Logic K Satisfiability Problem" Counter-Example-Guided Abstraction Refinement (CEGAR) has been very successful in model checking. Since then, it has been applied to many different problems. It is especially proved to be a highly successful practical approach for solving the PSPACE complete QBF problem. In this paper, we propose a new CEGAR-like approach for tackling PSPACE complete problems that we call RECAR (Recursive Explore and Check Abstraction Refinement). We show that this generic approach is sound and complete. Then we propose a specific implementation of the RECAR approach to solve the modal logic K satisfiability problem. We implemented both CEGAR and RECAR approaches for the modal logic K satisfiability problem within the solver MoSaiC. We compared experimentally those approaches to the state-of-the-art solvers for that problem. The RECAR approach outperforms the CEGAR one for that problem and also compares favorably against the state-of-the-art on the benchmarks considered. "Lille-Salle B21" |
Tue, June 6, 2017 to Fri, June 9, 2017 all day | Visit of Jean-Marc Talbot, Université de Marseille |
Fri, June 2, 2017 all day | Visit of Floris Geerts, University of Antwerp |
Fri, April 21, 2017 all day | Visit of Florent Capelli, London University |
Fri, March 24, 2017 all day | Visit of Charles Paperman, Université Paris 7 Université Paris 7 www.liafa.univ-paris-diderot.fr/~paperman/ INRIA Institut National Recherche Informatique Automatique 40 Avenue Halley, 59650 Villeneuve d'Ascq, France |
Wed, March 15, 2017 10:30 am 12:00 pm | Emmanuel Filliot, Université Libre de Bruxelles: "Automata, Logic and Algebra for Word Transductions" This talk will survey old and recent results about word transductions, i.e. functions mapping (finite) words to words. Connections between automata models (transducers), logic and algebra will be presented. Starting with rational functions, defined by (one-way) finite transducers, and the canonical model of bimachines introduced by Reutenauer and Schützenberger, the talk will also target the more expressive class of functions defined by two-way transducers and their equivalent MSO-based formalism. "Lille-Salle B21" |
Wed, March 15, 2017 all day | Visit of Emmanuel Filliot, Université Libre de Bruxelles |
Wed, February 1, 2017 11:00 am 12:30 pm | Pierre Bourhis: The Chase Inria Lille |
Fri, January 20, 2017 10:30 am 12:30 pm | Pierre Bourhis: "Tree Automata for Reasoning in Databases and Artificial Intelligence" In database management, one of the principal task is to optimize the queries to evaluate them efficiently. It is in particular the case for recursive queries for which their evaluation can lead to crawl all the database. In particular, one of the main question is to minimize the queries in order to avoid to evaluate useless parts of the query. The core theoretical question around this line of work is the problem of inclusion of a query in another. Interestedly, this question is related to an important question in IA which is to answer a query when the data is incomplete but rules are given to derive new information. This problem is called certain query answering. In both context, if both problem are undecidable in general, there are fragments based on guardedness that are decidable due to the fact there exists witness of the problems that have a bounded tree width and that their encoding in trees is regular. Furthermore, the queries can be translated in MSO. In both contexts, Courcelle’s Theorems imply the decidability of both problems. I will present to the different results on the translation of logic class of formula for our problems into tree automata to obtain tight bounds to the problems of inclusion of recursive queries or certain query answering. Inria Lille |
Wed, January 11, 2017 2:15 pm 3:25 pm | Michael vanden Boom, Oxford University : Decidable fixpoint logics Fixpoint logics can express dynamic, recursive properties, but often fail to have decidable satisfiability. A notable exception to this is the family of well-behaved "guarded" fixpoint logics, which subsume a variety of query languages and integrity constraints of interest in databases and knowledge representation. In this talk, I will survey some recent results about these logics. Lille B21 |
Mon, January 9, 2017 to Fri, January 13, 2017 all day | Visite Michael vanden Boom, Oxford University |
Fri, December 9, 2016 all day | Kickoff Headwork Paris MNHN |
Fri, November 18, 2016 10:30 am 12:00 pm | Florent Capelli Links Seminar "Lille-Salle B21" |
Fri, November 18, 2016 all day | Florent Capelli visit |
Tue, November 8, 2016 2:30 pm 4:30 pm | Seminar Link by Helmut Seidl: "Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable" Abstract: We show that equivalence of deterministic top-down tree-to-string transducers is decidable, thus solving a long standing open problem in formal language theory. We also present efficient algorithms for subclasses: polynomial time for total transducers with unary output alphabet (over a given top-down regular domain language), and co-randomized polynomial time for linear transducers, these results are obtained using techniques from multi-linear algebra. For our main result, we prove that equivalence can be certified by means of inductive invariants using polynomial ideals. This allows us to construct two semi-algorithms, one searching for a proof of equivalence, one for a witness of non-equivalence. "Lille-Salle B31 " |
Mon, November 7, 2016 2:00 pm 4:00 pm | PhD defense Adrien Boiret |
Fri, November 4, 2016 all day | colis general meeting Paris |
Thu, October 27, 2016 10:00 am 6:00 pm | Links day |
Thu, October 27, 2016 all day | links day |
Thu, October 20, 2016 2:00 pm 4:00 pm | Seminar Links by Vincent Hugot: "Top-Down Transducers for Data Trees" Abstract: Tree transducers have a wide range of application domains ranging from compiler construction, program analysis, and computational linguistics, to semi-structured databases and file system transformations. A common application of these domains is to specify and verify transformations of data trees, i.e., trees whose nodes are labeled by data values from an infinite domain. Most existing classes of tree transducers and their formal studies, however, are restricted to trees over finite signatures without data. In this paper, we lift the most prominent class of top-down tree transducers to data trees, such that its good properties are preserved. In particular, we show that top-down transducers for data trees have a decidable equivalence problem, without imposing any linearity restriction as in previous approaches based on symbolic top-down tree transducers. "Lille-Salle B21" |
Thu, October 13, 2016 2:00 pm 5:30 pm | comité de projet |
Thu, October 13, 2016 2:00 pm 3:00 pm | Seminar Christof Löding "Lille-Salle B21" |
Thu, October 13, 2016 to Fri, October 14, 2016 all day | visit christof löding |
Fri, September 30, 2016 all day | arrivée de Jose Lozano |
Thu, September 29, 2016 2:00 pm 4:00 pm | Seminar Links by Aurélien Lemay "Lille-Salle B21" |
Tue, September 27, 2016 all day | Ircica fetes ces 10 ans Lille |
Fri, September 9, 2016 2:00 pm 4:00 pm | Momar Sakho "Lille-Salle B21" |
Wed, September 7, 2016 11:00 am 12:00 pm | jason demagoj |
Wed, August 31, 2016 10:00 am 1:00 pm | Links Seminar by Domagoj Vrgoč: "Querying Graph with Data" "Lille-Salle B21" |
Thu, July 28, 2016 all day | Visit of Serge Abiteboul and Victor Vianu |
Mon, July 11, 2016 to Tue, July 12, 2016 all day | Aggreg meeting Marseille |
Mon, June 27, 2016 all day | Colis ANR project: general meeting Inria Paris, Salle 119 "Ada Lovelace" |
Fri, June 24, 2016 2:00 pm 4:00 pm | Fatima Belkouch: on the hypercube algorithm for conjunctive queries Abstract: We consider the problem of computing a conjunctive query on a large database in a parallel setting with p servers. Unlike traditional query processing, the complexity is no longer dominated by the number of disk accesses. Typically, a query is evaluated by a sufficiently large number of servers such that the entire data can be kept in the main memory of these servers. The dominant cost becomes that of communicating data and synchronizing among the servers. I will present some interesting results in [1, 2, 3, 4] dealing with the communication complexity of massively parallel computation of a query. The computation is performed in "rounds". First, I will present the Massively Parallel Communication (MPC) model to analyze the tradeoff between the number of rounds and the amount of communication required in a massively parallel computing environment. Then I will present the HyperCube (HC) algorithm that computes a full conjunctive query q in one round. I will discuss the communication complexity [2]. The main result is the optimal load O(m/p1/τ ) where τ is the fractional vertex cover of the hypergraph of q and m the input data size. References [1] Parallel Evaluation of Conjunctive Queries. Paris Koutris, Dan Suciu PODS2011 [2] Communication Steps for Parallel Query Processing. Paul Beame, Paris Koutris, Dan Suciu PODS2013 [3] Skew in Parallel Query Processing. Paul Beame, Paris Koutris Dan Suciu PODS'2014 [4] Worst-Case Optimal Algorithms for Parallel Query Processing. Paris Koutris, Paul Beame, Dan Suciu ICDT2016 "Lille-Salle B11" |
Thu, June 23, 2016 2:00 pm 3:30 pm | Victor Vianu in Polaris Auditorium IRCICA |
Thu, June 23, 2016 all day | victor vianu visit |
Mon, June 20, 2016 to Wed, June 22, 2016 all day | journee scientique inria à rennes |
Fri, June 17, 2016 9:00 am 12:30 pm | PhD Thesis Defense by Tom Sebastian: Evaluation of XPath Queries on XML streams with Networks of Early Nested Word Automata Abstract: The challenge that we tackle in this thesis is the problem of how to answer XPath queries on XML streams with low latency, full coverage, high time efficiency, and low memory costs. We first propose to approximate earli- est query answering for navigational XPath queries by compilation to early nested word automata. It turns out that this leads to almost optimal la- tency and memory consumption. Second, we contribute a formal semantics of XPath 3.0. It is obtained by mapping XPath to the new query language λXP that we introduce. We then show how to compile λXP queries to net- works of early nested word automata, and develop streaming algorithms for the latter. Thereby we obtain a streaming algorithm that indeed covers all of XPath 3.0. Third, we develop an algorithm for projecting XML streams with respect to the query defined by an early nested word automaton. Thereby we are able to make our streaming algorithms highly time efficient. We have implemented all our algorithms with the objective to obtain an industrially applicable streaming tool. It turns out that our algorithms outperform all previous approaches in time efficiency, coverage, and latency. |
Thu, June 16, 2016 2:00 pm 4:00 pm | Nicolas Bacquey Links seminar: Introduction to uniform periodical computation : leader election on periodical cellular automata "Lille-Salle B21" |
Thu, June 16, 2016 10:00 am 12:00 pm | Hubie Chen, Semainar and Visit "Lille-Salle B21" |